HDU 1686 Oulipo
题意：求模式串在主串中出现的次数【可重叠】
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIANSample Output
1
3
0
对代码中神奇的地方进行解释：
那么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
指针直接移动到红色部分进行匹配如何理解呢？
我们先不看最后那2个字符A和B，就可以发现最大前缀【指前缀和后缀的最长匹配长度】直接挪动到最大后缀那里了，为什么可以这样呢？因为前面都是显然不能够匹配成功的
可以向前移动一位试试看：
主串： A B A B A B C A B A B A A B
模式串： A B A B C A B A
我们先不看最后那2个字符A和B，可以看到现在是4长度的前缀与4长度的后缀比较，显然不
可匹配，因为最大匹配长度是3【指前缀和后缀的最长匹配长度】，显然再向前移也不行的
第一次长篇大论，若有错误或不明白之处，请指出
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;
}
补充：软件开发 , C语言 ,
