Algorithme de Knutt Morris Pratt
bonjour, j'ai implémenté l'algorithme de knutt morris pratt de recherche d'une sous-chaine dans une chaîne de caractère.
Voici la procédure d'initialisation du tableau ou l'on inscrit le motif à chercher:
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
| public void Init_tab(){
int i = 0;
int j = -1 ;
char c='\0';
tab_motif[0]=j;
while((motif.charAt(i)) != ('\0')){
if(motif.charAt(i)==c){
tab_motif[i+1]=j+1;
i++;
j++;
c=motif.charAt(j);
}
else{
if(j>0){
j=tab_motif[j];
}
else{
tab_motif[i+1]=0;
++i;
j=0;
}
c=motif.charAt(j);
}
if(i>=motif.length()){
break;
}
}
} |
Et voici la procédure de recherche de la sous chaine dans le motif :
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
| public boolean Rechercher (String com){
int m = 0;
int i = 0;
while (i<motif.length() && (m+i)<com.length()){
//while( com.charAt(m+i)!= '\0' && motif.charAt(i) != '\0'){
if(com.charAt(m+i)==motif.charAt(i)){
i++;
}
else {
if (tab_motif[i]==0 && tab_motif[1]!=com.charAt(m+i)){
m++;
}
else {
m+=i-tab_motif[i];
if(i>0){
i=tab_motif[i];
}
}
}
}
if(i==motif.length()){
System.out.println("trouvé");
return(true);
}
else {
System.out.println(" pas trouvé");
return(false);
}
}
} |
Le recherche marche correctement sauf quand par exemple j'ai comme commentaire
"J'aime lam er" il ya un espace entre m et er donc la recherche devrait retourner false si mon mot recherch" est "mer" pourtant la procédure me retourne true.
Est ce que ça vient de la ligne:
if (tab_motif[i]==0 && tab_motif[1]!=com.charAt(m+i)){
?
Merci d'avance pour votre aide
