hihocoder#1015：（KMP）

#include<iostream>#include<string>#include<cstring>#include<cmath>#include<cstdio>#include<cstdlib>#include<stdio.h>#include<algorithm>using namespace std;const int maxl=10010;int Next[maxl];string s,t;int n;int main(){	freopen("c.in","r",stdin);	freopen("c.out","w",stdout);		scanf("%d",&n);	for (int i=1; i<=n; i++)	{		cin>>t;		cin>>s;		int tlen=t.size();		int slen=s.size();				Next[0]=Next[1]=0;		int k=0;		for (int i=2; i<=tlen; i++)		{			while ( k && t[k]!=t[i-1] ) k=Next[k];			if ( t[k]==t[i-1] ) k++;			Next[i]=k;		}				k=0;		int ans=0;		for (int i=1; i<=slen; i++)		{			while ( k && t[k]!=s[i-1] ) k=Next[k];			if ( t[k]==s[i-1] ) k++;			if ( k==tlen ) ans++;		}				printf("%d/n",ans);	}		return 0;}