Code For NonGeek
Would you like to react to this message? Create an account in a few clicks or log in to continue.

String Matching KMP

Go down

String Matching KMP Empty String Matching KMP

Post  Admin Mon Sep 26, 2011 2:33 pm

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

Admin
Admin

Posts : 131
Join date : 2011-08-16

https://codefornongeek.forumotion.com

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum