#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

void get_next(char* p, int next[])
{
	int k = -1;
	int j = 0;
	next[0] = -1;
	int len = strlen(p);
	while (j < len)
	{
		if (k == -1 || p[j] == p[k])
		{
			j++;
			k++;
			if (p[j] != p[k])
			{
				next[j] = k;
			}
			else
			{
				next[j] = next[k];
			}
		}
		else
		{
			k = next[k];
		}
	}
}

int kmp(char* p, char* t, int next[])
{
	int ans = 0;
	int plen = strlen(p);
	int tlen = strlen(t);
	int i = 0, j = 0;
	while (i < tlen)
	{
		if (j == -1 || p[j] == t[i])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
		if (j == plen)
		{
			ans++;
			j = next[j];
		}
	}
	return ans;
}
char t[1000010], p[1000010];
int next[1000010];
int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		scanf("%s", p);
		scanf("%s", t);
		get_next(p, next);
		int ans = kmp(p, t, next);
		printf("%d\n", ans);
	}
	return 0;
}

• Re:【AC】kmp算法 (1121) 1561726052 2015-04-14 17:20:37