HDU 1686 Oulipo

http://acm.hdu.edu.cn/showproblem.php?pid=1686

题意：求模式串在主串中出现的次数【可重叠】

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

跟这个有相同点的题：http://972169909-qq-com.iteye.com/blog/1071548#

对代码中神奇的地方进行解释：



那么3的意义可以表示为

可见next[len2]的意义：前缀和后缀的最长匹配长度

现在就以这个为模式串模拟一下：

主串：    A B A B A B C A B A B A A B

模式串：       A B A B C A B A

匹配成功后下一步的情况应为：

主串：    A B A B A B C A B A B A A B

模式串：                         A B A B C A B A

指针直接移动到红色部分进行匹配

如何理解呢？
我们先不看最后那4个字符"BAAB"，就可以发现最大前缀【指前缀和后缀的最长匹配长度】直接挪动到最大后缀那里了，为什么可以这样呢？因为前面都是显然不能够匹配成功的
可以向前移动一位试试看：

主串：    A B A B A B C A B A B A A B

模式串：                      A B A B C A B A

我们先不看最后那4个字符"BAAB"，可以看到现在是4长度的前缀与4长度的后缀比较，显然不

可匹配，因为最大匹配长度是3【指前缀和后缀的最长匹配长度】，显然再向前移也不行的

第一次长篇大论，若有错误或不明白之处，请指出

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define L1 1000005
#define L2 10005

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

void get_next ()
{
	int j = 0, k = -1;
	next[0] = -1;
	while (j < len2)
	{
		if (k == -1 || p[j] == p[k])
		{
			j++, k++;
			next[j] = k;
		}
		else k = next[k];
	}
}
void kmp (int pos)
{
	int i = pos, 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];    //神奇之处，效率大增
	}
}
int main()
{
	int t;
	scanf ("%d", &t);
	while (t--)
	{
		res = 0;
		scanf ("%s%s", p, s);
		len1 = strlen (s);
		len2 = strlen (p);
		get_next ();
		kmp (0);
		printf ("%d\n", res);
	}
	return 0;
}