一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Input输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
Output输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
Sample Input
abcde a3
aaaaaa aa
#
Sample Output
0
3
题意：找两个字符串的最大匹配数
题解：用kmp每次把父串减去前面已经匹配好的，当无匹配时就直接退出
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; int Next[N],slen,plen;
string str,ptr; void getnext()
{
int k=-;
Next[]=-;
for(int i=;i<=slen-;i++)
{
while(k>-&&str[k+]!=str[i])k=Next[k];
if(str[k+]==str[i])k++;
Next[i]=k;
}
}
int kmp()
{
int k=-;
for(int i=;i<=plen-;i++)
{
while(k>-&&str[k+]!=ptr[i])k=Next[k];
if(str[k+]==ptr[i])k++;
if(k==slen-)return i-slen+;
}
return -;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
// cout<<setiosflags(ios::fixed)<<setprecision(2);
while(){
cin>>ptr;
if(ptr=="#")break;
cin>>str;
slen=str.size();
plen=ptr.size();
getnext();
int res=;
while(plen>=slen){
int ans=kmp()+;
if(ans==)break;
res++;
ptr=ptr.substr(ans+slen-,plen);
plen=ptr.size();
}
cout<<res<<endl;
}
return ;
}
第二个方法感觉更好，直接用kmp的特点直接跳到下一个匹配串
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; int Next[N],slen,plen,res;
string str,ptr; void getnext()
{
int k=-;
Next[]=-;
for(int i=;i<=slen-;i++)
{
while(k>-&&str[k+]!=str[i])k=Next[k];
if(str[k+]==str[i])k++;
Next[i]=k;
}
}
void kmp()
{
int k=-;
for(int i=;i<=plen-;i++)
{
while(k>-&&str[k+]!=ptr[i])k=Next[k];
if(str[k+]==ptr[i])k++;
if(k==slen-)
{
k=-;
res++;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
// cout<<setiosflags(ios::fixed)<<setprecision(2);
while(){
cin>>ptr;
if(ptr=="#")break;
cin>>str;
slen=str.size();
plen=ptr.size();
getnext();
res=;
kmp();
cout<<res<<endl;
}
return ;
}