# KMP Agorithm (Part 2 : Complete Algorithm)

Tue Feb 08 2022 12:05:47 GMT+0000 (UTC)

```import java.util.*;
import java.io.*;

class GFG {

static void fillLPS(String str, int lps[])
{
int n=str.length(),len=0;
lps[0]=0;
int i=1;
while(i<n){
if(str.charAt(i)==str.charAt(len))
{len++;lps[i]=len;i++;}
else
{if(len==0){lps[i]=0;i++;}
else{len=lps[len-1];}
}
}
}

static void KMP(String pat,String txt)
{
int N=txt.length();
int M=pat.length();
int[] lps=new int[M];
fillLPS(pat,lps);
int i=0,j=0;
while(i<N){
if(pat.charAt(j)==txt.charAt(i)){i++;j++;}

if (j == M) {
System.out.println("Found pattern at index " + (i - j));
j = lps[j - 1];
}
else if (i < N && pat.charAt(j) != txt.charAt(i)) {
if (j == 0)
i++;
else
j = lps[j - 1];
}
}
}

public static void main(String args[])
{   String txt = "ababcababaad",pat="ababa";
KMP(pat,txt);
}

} ```
content_copyCOPY

Complete KMP algorithm is discussed. This algorithm uses the LPS array. Input : -------- Text = "ababcababaad" Pattern ="ababa" Output: --------- Found pattern at index 5