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 :

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);
          }
 
      }
}
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