题目链接：
Description
The French author Georges Perec (1936�1982) once wrote a book, La
disparition, without the letter ‘e’. He was a member of the Oulipo
group. A quote from the book:
- Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair
- normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait
- voulu savoir où s’articulait l’association qui l’unissait au roman :
- stir son tapis, assaillant à tout instant son imagination, l’intuition
- d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit
- la vision, l’avision d’un oubli commandant tout, où s’abolissait la
raison : tout avait l’air normal mais…Perec would probably have scored high (or rather, low) in the
following contest. People are asked to write a perhaps even meaningful
text on some subject with as few occurrences of a given “word” as
possible. Our task is to provide the jury with a program that counts
these occurrences, in order to obtain a ranking of the competitors.
These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive ‘T’s is not unusual. And they never
use spaces.So we want to quickly find out how often a word, i.e., a given string,
occurs in a text. More formally: given the alphabet {‘A’, ‘B’, ‘C’, …,
‘Z’} and two finite strings over that alphabet, a word W and a text T,
count the number of occurrences of W in T. All the consecutive
characters of W must exactly match consecutive characters of T.
Occurrences may overlap.
Input
The first line of the input file contains a single number: the number
of test cases to follow. Each test case has the following format:One line with the word W, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with
1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W). One
line with the text T, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with |W|
≤ |T| ≤ 1,000,000.
Output
For every test case in the input file, the output should contain a
single number, on a single line: the number of occurrences of the word
W in the text T.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
题目大意：
第一行表示一共多少组数据,每组数据两行，接下来输入数据
第二行为一个字符串ａ
第三行为一个字符串ｂ
ａ
b
a
b …..要求出ａ在ｂ中出现多少次，可以重叠： 例：aza 在azazaza中出现了３次
思路：
ｋｍｐ 每次匹配到一个相同的之后，将ｊ至于ｎｅｘｔ[j-1]，继续比较。开始我想着因为可以有重叠，就让主串指针回溯i =
i-j+1,ｉ再++，发现超时，后来看别人代码，ｉ不回溯，每次匹配成功后count++,之后继续，直到遍历完整个主串，一定要记住，kmp中主串指针就是不需要回溯！！！还是理解不到位
/*************************************************************************
> File Name: hdu_1686_kmp.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月13日 星期日 22时35分44秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 50086;
const int M = 1000009;
char a[N];
char b[M];
int nxt[N];
void getnxt(int m)
{
int k = 0;
memset(nxt, 0, sizeof(0));
for(int i = 1; i < m; i++)
{
while(k && a[i] != a[k]) k = nxt[k-1];
if(a[i] == a[k]) k++;
nxt[i] = k;
}
}
int kmp()
{
getnxt(strlen(a));
int j = 0;
int len = strlen(b);
int count = 0;
for(int i = 0; i < len; i++)
{
while(j && b[i] != a[j]) j = nxt[j-1];
if(b[i] == a[j]) j++;
if(j == strlen(a) ) count++, j = nxt[j-1];
// 与没匹配上的操作一样，ｊ置与nxt[j-1]
}
return count;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%s", a);
scanf("%s", b);
printf("%d\n", kmp());
}
return 0;
}