题目大意：
求字符串A在字符串B中出现的次数。
思路：
KMP板题，用Hash也可水过~要学习KMP可参考http://blog.csdn.net/u011564456/article/details/20862555
代码：
KMP：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 char s1[10009],s2[1000009]; 7 int next[10009]; 8 9 int main() 10 { 11 int n,i,l1,l2,j,ans; 12 scanf("%d",&n); 13 while (n--) 14 { 15 scanf("%s%s",s1,s2); 16 l1=strlen(s1),l2=strlen(s2); 17 for(j=next[0]=0,i=1;i<l1;i++) 18 { 19 for (;j && s1[j]^s1[i];j=next[j-1]); 20 if (s1[i]==s1[j]) j++; 21 next[i]=j; 22 } 23 for (i=j=ans=0;j<l2;j++) 24 { 25 for (;i && s1[i]^s2[j];i=next[i-1]); 26 if (s1[i]==s2[j]) i++; 27 if (i==l1) ans++,i=next[i-1]; 28 } 29 printf("%d\n",ans); 30 } 31 return 0; 32 }Hash：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int S=999984,mod=1000000007,N=10009,M=1000009; 6 char s1[N],s2[M]; 7 long long Hash1[N],Hash2[M],mi[M]; 8 9 int gethash(int l,int r) 10 { 11 return (Hash2[r]-Hash2[l-1]*mi[r-l+1]%mod+mod)%mod; 12 } 13 14 int main() 15 { 16 int n,i,j,l1,l2,ans; 17 for (mi[0]=i=1;i<=M;i++) mi[i]=mi[i-1]*S%mod; 18 scanf("%d",&n); 19 while (n--) 20 { 21 scanf("%s%s",s1+1,s2+1); 22 l1=strlen(s1+1),l2=strlen(s2+1); 23 for (i=1;i<=l1;i++) Hash1[i]=(Hash1[i-1]+s1[i])*S%mod; 24 for (i=1;i<=l2;i++) Hash2[i]=(Hash2[i-1]+s2[i])*S%mod; 25 for (ans=0,i=1;i<=l2-l1+1;i++) 26 if (gethash(i,i+l1-1)==Hash1[l1]) ans++; 27 printf("%d\n",ans); 28 } 29 return 0; 30 }
转载于:https://www.cnblogs.com/HHshy/p/5734100.html
相关资源：JAVA上百实例源码以及开源项目