I am trying to solve a string matching question mentioned here. I recently learned the Knuth–Morris–Pratt algorithm and tried to implement it to solve this question. But I am getting a TLE for this code:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Gogl {
static int count=0;
public static void main(String[] args)
{
MyScannergogl sc=new MyScannergogl();//used own input function
String text=sc.next();
String pattern=sc.next();
KMP(text,pattern);
System.out.println(count);
}
static int[] computeTempArray(String pattern)
{
int lsp[]=new int[pattern.length()];
int index=0;
int i;
for(i=1;i<pattern.length();)
{
if(pattern.charAt(i)==pattern.charAt(index))
{
lsp[i]=lsp[index]+1;
i++;
index++;
}
else
{
if(index!=0)
{
index=lsp[i-1];
}
else
{
lsp[i]=0;
i++;
}
}
}
return lsp;
}
public static void KMP(String text,String pat)
{
int lsp[]=computeTempArray(pat);
int i=0;
int j=0;
while(i<text.length() )
{
if(text.charAt(i)==pat.charAt(j))
{
i++;
j++;
}
else
{
if(j!=0)
{
j=lsp[j-1];
}
else
{
i++;
}
}
if(j==pat.length())
{
count++;
j=0;
}
}
}
}
I couldn't understand where am I wrong. Whether I have not properly implemented the algorithm or is there some other problem I am not aware of. As I know that KNP is really fast so should have crossed the time limit.