récupérer la partie commune d'une liste de String

Version imprimable

17/04/2007, 15h16
Kanter

récupérer la partie commune d'une liste de String

Bonjour,

j'essaie, en vain vu mon niveau en algo, de coder une fonction qui va extraire la partie commune de toutes les chaines issues de la liste.

Ex :
Liste[0] : 1-2-3-4-5-X-AA-BB-CC
Liste[1] : 1-2-3-4-5-6-AA-BB-CC
Liste[2] : 1-2-3-4-5-6-00-BB-CC
Liste[3] : 1-2-3-4-5-6-AA-00-CC
Liste[4] : 1-2-3-4-5-6-AA-BB-DD

la partie commune est : 1-2-3-4-5

ca peut donner quoi en algo...

Merci les enfants...

Papy Mouzo.
17/04/2007, 15h42
PadawanDuDelphi

Salut,

C'est plus un problème d'algo que de Delphi...Mais en gros il faut,
Lire le premier caractère de ta première liste et le comparer à tous tes premiers caratères de ta list... Si c'est ok, passer à la seconde; etc...
Avec ca tu recupère ton indice de partie commune, donc ta chaî,e commune.

A+.
17/04/2007, 15h45
mayloshi
Tu la connais au préalable, ta sous chaîne à extraire? Si oui:
1. algo de recherche de la sous chaine dans la liste (avec pos(souschaine,chaine))
2. si tous les pos sont egaux (stricte egalité, meme la position dans la chaine) ou s'ils sont tous différents de zero (juste présence de la sous chaine, comme dans un moteur de recherche); extraire la sous chaine selon les positions obtenue (delete(chaine,position,longueursouschaine))
Surtout n'oublie pas de stocker les positions dans une autre table.
17/04/2007, 15h49
Kanter

En reponse à PadawanDuDelphi:

Je vais faire mon bobo,
mais c'est ce que j'avais déjà établi avant... Je pensais que quelqu'un allait me dire... "c'est super méga simple ! Tête de navet creux !" mais a priori... ca ne l'est pas tant que ca !

PadawanDuDelphi ne serais tu pas un fan de Ulysse 31 ? en rappport avec ta citation ?

@mayloshi :
justement non, je ne connais pas la sous chaine...
17/04/2007, 16h07
ShaiLeTroll

Il existe plusieurs algo, on peut effectivement,
- comparer les caractères, un par un, sur chaque ligne ...
- comparer deux à deux chaque chaines et extraire ainsi au fur et à mesure les chaines communes ...

Pour les performances, tout dépend du nombre de ligne, et de la chance d'avoir consécutivement deux chaines très différentes ...

j'ai déjà ce genre de fonction en stock, si tu veux, si tu préfère juste l'algo (méthode 2)

tu as une fonction qui renvoie la partie commune entre deux chaines (j'ai un souvenir de cela dans Delphi, mais c'est pas une fonction compliqué à refaire)

et tu parcours ta liste à partir du 2ème item (le premier étant conservé comme première chaine commune), tu compare la chaine considéré comme commune au 2eme, item, et tu affecte la comparaison à chaine considéré comme commune, et tu compare jusqu'au dernier item ...

Citation:

Envoyé par Kanter

PadawanDuDelphi ne serais tu pas un fan de Ulysse 31 ? en rappport avec ta citation ?

A mon avis c'est plus Stargate la réplique :P

sinon un petit code pas optimisé
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function SearchCom (lst : TStringList) : String; var i,j : integer; MaChaine,sTmp : String; begin MaChaine := lst.Strings[0]; for i := 1 to lst.count -1 begin sTmp := lst.Strings[i]; if Pos(MaChaine,sTmp ) = -1 then begin for j:= 0 to Length(MaChaine) do if MaChaine[j] <> sTmp[j] then break; MaChaine := Copy(MaChaine,1,j-1); end; // if end; Result := MaChaine; end;
Code non testé qui nécessite quelques modifications mais qui dans l'esprit correspond à ce que tu veux faire.

je pense avoir trouver qqchose :
algo :

Code:

1
2
3
4
5
6
7
8
9
10
    Reference := Liste[0];
 
    for Jndex := 1 to Length(Reference) do
    begin
        for Index := 1 to Liste.Count- 1 do
            if Reference[Jndex] <> Liste[Index][Jndex] then
            begin
                Showmessage(Copy(Reference,1,Jndex));
            end;
    end;

et le plus etrange (a part quelques recalages d'index et sortie de boucles for) ca fonctionne... Etrange... je le tenais depuis le debut... Dohhhhhh

17/04/2007, 16h21
Rayek

Regarde un post plus haut :P
17/04/2007, 16h22
PadawanDuDelphi

Citation:

Envoyé par malatar

A mon avis c'est plus Stargate la réplique

Tout à fait...
Shal kek nem ron! mon frère. :mrgreen:

Citation:

Envoyé par Kanter

et le plus etrange (a quelque recalage d'index et sorti de boucle for) ca fonctionne... Etrange... je le tenais depuis le debut... Dohhhhhh

T'as pas fini de noter des comportements étranges avec la programmation, mais en tout cas l'essentiel c'est que ça fonctionne à la fin...

A+.

Si cela t'intéresse toujours, voici deux fonctions pour faire ta recherche ... à toi de tester quels algo est le plus rapide ...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function ExtractCommonString(const S1, S2: string): string;
var
  SLen, SLen1, SLen2 : Integer;
  I, IEnd: Integer;
begin
  SLen1 := Length(S1);
  SLen2 := Length(S1);
  if SLen1 < SLen2 then
    SLen := SLen1
  else
    SLen := SLen2;
 
 IEnd := SLen;
 for I := 1 to SLen do
   if S1[I] <> S2[I] then
   begin
     IEnd := I - 1;
     Break;
   end;
 
 if IEnd > 0 then
   Result := Copy(S1, 1, IEnd)
 else
   Result := '';
end;
 
function ExtractCommonStringInList(Strings: TStrings): string;
var
  I: Integer;
begin
  if Assigned(Strings) and (Strings.Count > 0) then
  begin
    Result := Strings[0];
    for I := 1 to Strings.Count - 1 do
    begin
      Result := ExtractCommonString(Result, Strings[I]);
      if Length(Result) = 0 then
        Exit;
    end;
  end else
    Result := '';
end;

17/04/2007, 17h03
Kanter

Ca roule... Merci...
Bon au max, je peux avoir 200 chaines... donc ca roule...

merci à vous tous...

Voici encore une variante pour l'embarras de choix :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function ExtraisPrefixeCommunDans(var Liste : Array of string): string;
var      clpc : string; li,co : integer; Stop : boolean; ci,ct : char;
begin    clpc:=Liste[low(Liste)];
         for li:=low(Liste) to high(Liste)                         // Recherche
         do if length(Liste[li])<length(clpc)                      // de la chaine
         then begin clpc:=Liste[li]; Liste[li]:=Liste[low(Liste)]; // la plus courte
                    Liste[low(Liste)]:=clpc; end;                  // 5 lignes supprimables si toutes le chaines
         if clpc='' then begin Result:=clpc; EXIT; end;            // sont <>'' et de même longueur
         // Recherche Préfixe commun :
         co:=0; Stop:=false;
         Repeat inc(co); ci:=clpc[co]; li:=low(Liste);
                repeat inc(li);
                       if Liste[li][co]<>ci then begin Stop:=true; dec(co); end;
                until (li=high(Liste)) or (Stop);
         Until (co=length(clpc)) or (Stop);
         If Stop=false then Result:=clpc else Result:=copy(clpc,1,co);
end;

... testé : renvoie 1-2-3-4-5- avec les données de l'exemple initial.