### KMP implementation

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051`` ``````#include using namespace std; int *prefunc(string p){ int m=p.size(), k=0; int *pi=new int[m]; pi[1]=0; for(int q=2;q0 && p[k+1]!=p[q]){ k=pi[k]; } if(p[k+1]==p[q]) k=k+1; pi[q]=k; } return pi; } int KMP_Matcher(string s, string p){ int *pi; int n=s.size(); int m=p.size(); pi=prefunc(p); int q=0; for(int i=1;i<=n;i++){ while(q>0 && p[q+1]!=s[i]){ q=pi[q]; } if(p[q+1] == s[i]){ q++; } if(q==m){ return(i-m); } q=pi[q]; } return 0; } void main(){ int x; string s="bacbabababacaab"; string p="ababaca"; x=KMP_Matcher(s,p); if(x==0) cout<<"\nNo match found\n"; else cout<<"\nPattern occurs with shift "<
What specific problem do you want help with? What error(s) are you getting and when?

there is a garbage value in q of KMP_Matcher
if(p[q+1]==s[i])
i think at this line is some problem
Hi,

I still haven't worked out the logic (no time or energy :0), so I don't know what you're trying to accomplish.

Can you explain what you're trying to do, that speeds things up for everyone.

In the mean time, look at lines 6 and 10-12:
 ``12345`` ``````int m=p.size(), k=0; while(k>0 && p[k+1]!=p[q]){ k=pi[k]; }``````

That while loop will never run, because you initialise k to 0, you never change it, and then ask the loop to only run when k > 0.

You've done the same thing in lines 26 - 30.

Also, check for zero-based indexing and memory leaks...

Topic archived. No new replies allowed.