/*
tju 3275(Windy's S), zju2006(Glass Beads),
*/
//6696446 Xredman 3461 Accepted 2296K 266MS C++ 971B 2010-04-06 20:49:57 

#include <iostream>
#include <string>
using namespace std;

const int N = 1000004;
int next[N];


void getNext(string T)
{
	int j, k;
	int len = T.length();
	j = 0; k = -1; next[0] = -1;
	while(j < len)
		if(k == -1 || T[j] == T[k])
			next[++j] = ++k;
		else
			k = next[k];

}

int KMP_Count(string S, string T)
{
	int ans = 0;
	int slen = S.length(), tlen = T.length();
	int i, j = 0;
	if(slen == 1 && tlen == 1)
	{
		if(S[0] == T[0])
			return 1;
		else
			return 0;
	}
	getNext(T);
	for(i = 0; i < slen; i++)
	{
		while(j > 0 && S[i] != T[j])
			j = next[j];
		if(S[i] == T[j])
			j++;
		if(j == tlen)
		{
			ans++;
			j = next[j];
		}
	}
	return ans;
}
int main()
{
	string S, T;
	int TT;
	cin>>TT;
	while(TT--)
	{
		cin>>T>>S;
		cout<<KMP_Count(S, T)<<endl;
	}
	return 0;
}

• 相关文章
• 全局相关文章