String Matching KMP
Page 1 of 1
String Matching KMP
public int match(byte[] T, byte[] P){
int n=T.length;
int m=P.length;
if(m>n)
return -1;
int[] f=selfOverlap(P,m);
int j=0;
for(int i=0; i<n;){
while(P[j]==T[i]){
i++;j++;
if(j==m) return i-m;
if(i==n) return -1;
}
if(j==0) i++;
else j=f[j-1];
}
return -1;
}
public int[] selfOverlap(byte[] P, int m){
int[] f=new int[m];
for(int j=0,i=1;i<m;){
while(P[j]==P[i]){
f[i]=j+1;
i++;j++;
if(i==m) return f;
}
if(j==0) i++; else j=f[j-1];
}
return f;
}
int n=T.length;
int m=P.length;
if(m>n)
return -1;
int[] f=selfOverlap(P,m);
int j=0;
for(int i=0; i<n;){
while(P[j]==T[i]){
i++;j++;
if(j==m) return i-m;
if(i==n) return -1;
}
if(j==0) i++;
else j=f[j-1];
}
return -1;
}
public int[] selfOverlap(byte[] P, int m){
int[] f=new int[m];
for(int j=0,i=1;i<m;){
while(P[j]==P[i]){
f[i]=j+1;
i++;j++;
if(i==m) return f;
}
if(j==0) i++; else j=f[j-1];
}
return f;
}
Similar topics
» String Matching
» Permutations of a String
» Reverse a String
» convert a string into integer
» Given a string, find all of its permutations
» Permutations of a String
» Reverse a String
» convert a string into integer
» Given a string, find all of its permutations
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum