「LOJ#10043」「一本通 2.2 例 1」剪花布条 （KMP

 1 /*
 2 编号     题目     状态     分数     总时间     内存     代码 / 答案文件     提交者     提交时间
 3 #224299     #10043. 「一本通 2.2 例 1」剪花布条    Accepted     100     340 ms     252 KiB     C++ / 725 B     qwerta     2018-10-10 15:37:39
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 using namespace std;
 8 int nxt[1003];
 9 int main()
10 {
11     //freopen("a.in","r",stdin);
12     string s,t;
13     while(cin>>s)
14     {
15         if(s.length()==1&&s[0]==‘#‘)break;
16         cin>>t;
17         int k=-1,lens=s.length(),lent=t.length();
18         nxt[0]=-1;
19         for(int i=0;i<lent;++i)
20         {
21             while(k!=-1&&t[i]!=t[k+1])k=nxt[k];
22             if(t[i]==t[k+1])k++;
23             nxt[i+1]=k;
24         }
25         k=-1;
26         int ans=0;
27         for(int i=0;i<lens;++i)
28         {
29             while(k!=-1&&s[i]!=t[k+1])k=nxt[k];
30             if(s[i]==t[k+1])k++;
31             if(k==lent-1){ans++;k=-1;}
32         }
33         cout<<ans<<endl;
34     }
35     return 0;
36 }