Проблема в реализации алгоритма Кнута Морриса Пратта

Question

Я пытаюсь реализовать алгоритм Кнута Морриса Пратта для поиска по шаблону в Java, но он не дает никакого результата. Код генератора prefixTable работает нормально, как я его проверил, но основной код для поиска не работает

 public void KMPAlgorithm(String T, String P){
           int pi[]= prefixFinder(P);
           int n=T.length();
           int m=P.length();
           int q=0;
           for(int i=0; i<m; i++)System.out.print(pi[i]+"  ");
           for(int i=0; i<n; i++){

               while(q>0 && P.charAt(q)!=T.charAt(i)){
                   q=pi[q-1];
               }
               if(P.charAt(q)==T.charAt(i)){
                   q++;
               }


               if(q==(m-1)){System.out.println("Pattern occurs at "+(i-(m-1)));
                 q=pi[q];
               }


           }

А вот и алгоритм префиксного генератора

private int[] prefixFinder(String P){
           int m=P.length();
           int pi[]= new int[m];
          pi[0]=0;
          int k=0;
          for(int i=1;i<m; i++){
              while( k>0 && P.charAt(k)!=P.charAt(i)){
                  k=pi[k];
              }
              if(P.charAt(k)==P.charAt(i)){
                  k++;

              }
              pi[i]=k;
          }


           return pi;
       }

В качестве вывода он не дает пробела, указывающего, что он не нашел шаблона в некоторых граничных случаях

Answer 1

Ваша переменная q не проверяла последнюю букву, потому что вы меняли q, когда она доходила до m-1, а не m. Так что эта строка должна измениться с этого на

 if(q==(m-1)){System.out.println("Pattern occurs at "+(i-(m-1)));
             q=pi[q];
           }

 if(q==(m)){System.out.println("Pattern occurs at "+(i-(m-1)));
             q=pi[q];
           }

Кроме того, так как ваш q теперь в конце, вам также нужно изменить

q=pi[q];

в

 q=pi[q-1];