import java.io.*;
public class KMP2
{
String text = null, pattern = null;
int m,n,p,q=0,k;
int pie[];
KMP2() throws IOException{
System.out.print("\nEnter the string : ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
text = br.readLine();
System.out.print("\nEnter the pattern to be searched : ");
pattern = br.readLine();
n=text.length();
m=pattern.length();
pie=new int[m+1];
}
public void compute_prefix()throws IOException
{
pie[0]=0;
k=0;
for(q=1;q<m;q++)
{
while(k>0 && pattern.charAt(k) !=pattern.charAt(q))
k=pie[k-1];
if(pattern.charAt(k)==pattern.charAt(q))
k=k+1;
pie[q]=k;
}
}
public void find_string() throws IOException
{
compute_prefix();
System.out.print(" PI values : ");
for(int i=0;i<m;i++)
System.out.print(" "+pie[i]);
q=0;
for(int i=0;i<n;i++)
{
while(q>0 && pattern.charAt(q)!=text.charAt(i))
q=pie[q-1];
if(pattern.charAt(q)==text.charAt(i))
q=q+1;
if(q==m){
System.out.println("\nPattern occurs at "+(i-m+1)+" position");
return;
}
}
System.out.println("\nPattern not found");
}
public static void main(String args[]) throws IOException
{
KMP2 r=new KMP2();
r.find_string();
}
}
public class KMP2
{
String text = null, pattern = null;
int m,n,p,q=0,k;
int pie[];
KMP2() throws IOException{
System.out.print("\nEnter the string : ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
text = br.readLine();
System.out.print("\nEnter the pattern to be searched : ");
pattern = br.readLine();
n=text.length();
m=pattern.length();
pie=new int[m+1];
}
public void compute_prefix()throws IOException
{
pie[0]=0;
k=0;
for(q=1;q<m;q++)
{
while(k>0 && pattern.charAt(k) !=pattern.charAt(q))
k=pie[k-1];
if(pattern.charAt(k)==pattern.charAt(q))
k=k+1;
pie[q]=k;
}
}
public void find_string() throws IOException
{
compute_prefix();
System.out.print(" PI values : ");
for(int i=0;i<m;i++)
System.out.print(" "+pie[i]);
q=0;
for(int i=0;i<n;i++)
{
while(q>0 && pattern.charAt(q)!=text.charAt(i))
q=pie[q-1];
if(pattern.charAt(q)==text.charAt(i))
q=q+1;
if(q==m){
System.out.println("\nPattern occurs at "+(i-m+1)+" position");
return;
}
}
System.out.println("\nPattern not found");
}
public static void main(String args[]) throws IOException
{
KMP2 r=new KMP2();
r.find_string();
}
}
No comments:
Post a Comment