# HDU 1686 Oulipo

2011-06-21

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

C++代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L1 1000005
#define L2 10005

int len1, len2, next[L2], res;
char s[L1], p[L2];

void get_next ()
{
int k = -1, j = 0;
next[0] = -1;
while (j < len2) //这里必须要推导出next[len2]
{
if (k == -1 || p[k] == p[j])
{
j++, k++;
if (p[k] != p[j])
next[j] = k;
else next[j] = next[k];
}
else k = next[k];
}
/*for (j = 0; j <= len2; j++)
cout << next[j] << ;
cout << endl;*/
}
void kmp ()
{
int i = 0, j = 0;
while (i < len1 && j < len2)
{
if (j == -1 || s[i] == p[j])
i++, j++;
else j = next[j];
if (j >= len2)
res++, j = next[j]; //灰常神奇的地方，用到next[len2]，效率大大提高
}
}
int main()
{
int t;
scanf ("%d", &t);
while (t--)
{
scanf ("%s%s", p, s);
len1 = strlen(s);
len2 = strlen(p);
res = 0;
get_next();
kmp ();
printf ("%d ", res);
}
return 0;
}