1 /* *********************************************** 2 Author        :Sun Yuefeng 3 Created Time  :2016/10/31 19:02:08 4 File Name     :kmp.cpp 5 ************************************************ */ 6  7 #include<cstdio> 8 #include<iostream> 9 #include<algorithm>10 #include<cmath>11 #include<cstring>12 #include<string>13 #include<bitset>14 #include<map>15 #include<set>16 #include<stack>17 #include<vector>18 #include<queue>19 #include<list>20 #define M(a,b) memset(a,b,sizeof(a))21 using namespace std;22 typedef long long ll;23 const int inf=0x3f3f3f3f;24 const int maxn=1005;25 const int mod=1e7+7;26 int dx[8]= {0,0,1,-1,1,-1,1,-1};27 int dy[8]= {1,-1,0,0,-1,1,1,-1};28 29 char str[maxn];30 char f[maxn];31 int _next[maxn];32 33 /************************************34 next数组的含义就是：35 第0位的默认为036 以当前字符为结尾的字符串的最长公共前后缀长度37 例如：38 loc  0 1 2 3 4 5 639 str  A B C A B C D40 next 0 0 0 1 2 3 041 *************************************/42 43 void kmp(char str[],int len) //预处理next数组44 {45     int i=0,j=-1;46     _next[0]=-1;47     while(i<len)48     {49         while(-1!=j&&str[i]!=str[j]) j=_next[j];50         i++,j++;51         _next[i]=j;52     }53 }54 55 int cnt(char x[],int lenx,char y[],int leny) //查找56 {//x是模式串 y是主串57     int i=0,j=0,ans=0;58     M(_next,0);59     kmp(f,strlen(f));60     while(i<leny)61     {62         while(-1!=j&&y[i]!=x[j]) j=_next[j];63         i++,j++;64         if(j>=lenx)65         {66             ans++;67             j=0;68             //j=next[j];69             //如果换成上面这句的话 模式串是可以重复的70         }    71     }72     return ans;73 }74 75 int main()76 {77     //freopen("in.txt","r",stdin);78     //freopen("out.txt","w",stdout);79     while(cin>>str)80     {81         if(str[0]==‘#‘) break;82         cin>>f;83         cout<<cnt(f,strlen(f),str,strlen(str))<<endl;84     }85     return 0;86 }