本题就是给出非常多对字符串，然后问一个字符串在另外一个字符串出现的次数。

就是所谓的Strstr函数啦。

Leetcode有这道差点儿一模一样的题目。

使用KMP算法加速。算法高手必会的算法了。

另外看见讨论说什么使用KMP还超时，最大可能是没有真正理解next table的含义，写了错误的代码，故此尽管自己执行结果正确，可是却没有真正发挥next table的作用。使得算法退化为暴力法了，所以执行正确，但超时。

KMP參考： http://blog.csdn.net/kenden23/article/details/14178121

#include 
     
      #include 
      
       const int MAX_N = 10001;const int MAX_T = 1000001;char word[MAX_N];char text[MAX_T];int nextTbl[MAX_N];int wn, tn;int getTimes(){	int ans = 0;	int i = 0, j = 0;	//i为text的当前下标，j为word的当前下标	for (; i-j <= tn-wn; i++)	{		if (text[i] == word[j])		{			j++;			if (j == wn)			{				ans++;				j = nextTbl[j-1];			}		}		else if (j > 0)		{			j = nextTbl[j-1];			i--;		}	}	return ans;}void genTbl(){	memset(nextTbl, 0, sizeof(int) * (wn));	int i = 1, j = 0;	while (i < wn)	{		if (word[i] == word[j]) nextTbl[i++] = ++j;		else if (j > 0) j = nextTbl[j-1];		else i++;	}}int main(){	int T;	scanf("%d", &T);	getchar();	while (T--)	{		gets(word);//fgets(word, MAX_N, stdin);//fgets会在末尾保留'\n'		gets(text);//fgets(text, MAX_T, stdin);		wn = strlen(word);		tn = strlen(text);		genTbl();		printf("%d\n", getTimes());	}	return 0;}