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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 :
Le recherche marche correctement sauf quand par exemple j'ai comme commentaire
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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); } } }
"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
Partager