Issue in implementing knuth morris pratt algorithm

Question

I am trying to implement Knuth Morris Pratt Algorithm for pattern searching in java but it is not giving any result The prefixTable generator code runs fine as i have checked it but the main code for searching does not work

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


           }

And here is the Prefix Generator Algorithm

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

As an output it is giving no blank indicating that it found no pattern on some boundary cases

Answer 1

Your q variable was not getting to check the last letter because you were changing q when it was getting to m-1 not m. So this line needs to change from this to

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

Also since your q is now at the end you also need to change

q=pi[q];

to

 q=pi[q-1];