学步园

kmp的应用，求一个模式串在文本串中出现了几次

如果发现一个匹配后,令j=next[j]即可，即再接下去尝试匹配

代码：

#include<iostream><br /> #include<memory.h><br /> #include<string><br /> #include<cstdio><br /> #include<algorithm><br /> #include<math.h><br /> #include<stack><br /> #include<queue><br /> using namespace std;<br /> char p[10005];<br /> char t[1000005];<br /> int next[10005];<br /> void get_next(int n)<br /> {<br /> int i,j;<br /> next[1]=j=0;<br /> //cout<<p+1<<endl;<br /> for(i=2;i<=n;i++)<br /> {<br /> while(j>0&&p[j+1]!=p[i])<br /> j=next[j];<br /> if(p[j+1]==p[i])<br /> j=j+1;<br /> next[i]=j;<br /> }<br /> }<br /> void kmp()<br /> {<br /> int cnt=0,i,j,len=strlen(t+1),tar=strlen(p+1);<br /> get_next(tar);<br /> j=0;<br /> for(i=1;i<=len;i++)<br /> {<br /> //cout<<"j="<<j<<endl;<br /> while(j>0&&p[j+1]!=t[i])<br /> {</p> <p> j=next[j];<br /> }<br /> //cout<<p+1<<endl;<br /> if(p[j+1]==t[i])<br /> {<br /> //cout<<t[j+1]<<" "<<t[i]<<endl;<br /> j++;<br /> //cout<<"j="<<j<<endl;<br /> }<br /> //cout<<i<<" "<<j<<endl;<br /> if(j==tar)<br /> {<br /> cnt++;<br /> j=next[j];<br /> }<br /> }<br /> cout<<cnt<<endl;<br /> }<br /> int main()<br /> {<br /> int i,j,n;<br /> scanf("%d",&n);<br /> while(n--)<br /> {<br /> scanf("%s%s",p+1,t+1);<br /> kmp();<br /> }<br /> return 0;<br /> }