按照我们平常的思维，会直接暴力，把S1中每一段都和S2去比较一次
但是如果字符串的长度很长呢？时间复杂度是O(N^2),给你个100万长度的，那你到哪一年去了啊？这时，请想到KMP算法
假如有两个字符串
S1：aaaaaaas
S2：aaas
一看就知道，有很多的比较是没有意义的，直接忽略都可以，KMP讲的就是最长相同前后缀（找不到名词，自己取的- -！）
就是在S2中匹配到某一个字符的时候，它前面的字符都是匹配成功了的，KMP的精髓就是在它前面已经匹配成功的字符串里
面做文章，比如上面的S2，假如是‘s‘以前的都匹配好了，然后从它前面的那个串"aaa"我们能发现最长相同前后缀是"aa"（
前后缀不包括串本身）在‘s‘匹配失败时可以把后缀当前缀来表示前缀已经匹配成功，这样就直接匹配前缀后面的那个字符，
这样就省去了那些没意义的比较。
这时引用一个next数组，它就是自己定义的一个int型数组，这个数组的用处就是记录一个下标，在当前点匹配失败时不用直
接跳回匹配它时已经确认匹配成功的字符串里面的最长前缀的后一个字符的下标。
一句话，关键就是找出最长相同前后缀，作用是当后缀匹配成功后在匹配失败可以直接确定用与后缀匹配的那段已经和前缀
匹配成功，这时用那个与后缀后面那个字符匹配失败的字符去与前缀后面的那个字符匹配，这样就完成了一轮的跳转。
这里可以了解到，求S2的next数组才是关键,直接讲解函数更好理解
void getnext(char s[],int l) //求S2的next数组
{
int i=0,j=-1;next[i]=j;
//初始化第一个字符的next为一个特殊值，因为第一个都没匹配成功，肯定还是只能用第一个去匹配别的啦
//i是所求的next数组当前位置的下标，j用来找最长前缀的位置
while(i<l)
if(j==-1||s[i]==s[j]) next[++i]=++j;
//如果j是特殊值或者是匹配成功就可以确定下来这个next值了
//要先+1，因为i是已经匹配成功的串的最后一个位置，j是最长前缀最后一个位置
else j=next[j];
//否则就跳到当前位置下标next指向的位置
//这里是重点，next值的是该位置之前的串的最长前后缀，求某点的next，就用它前面那个点的next去一个一个next的跳，这样只会最长缀越来越短，直到有一个能和这一点的前面那个字符匹配的点或者是跳到那个特殊值
}
比如这个S2的next应该是这么对应的
下标 0 1 2 3
S2： a a a s
next： -1 0 1 2
下面来详细模仿过程
i=0,j=-1
下标 0 1 2 3
S2： a a a s
next： -1
因为j=-1满足条件，i=1,j=0,next[1]=0
下标 0 1 2 3
S2： a a a s
next： -1 0
因为s[i]=s[j]满足，i=2,j=1,next[2]=1
下标 0 1 2 3
S2： a a a s
next： -1 0 1
因为s[i]=s[j]满足，i=3,j=2,next[3]=2
下标 0 1 2 3
S2： a a a s
next： -1 0 1 2
其实还可以求出下标为4的位置的next值，只不过匹配只要求到3，但是位置为4的那个也是很重要的，这在next数组的应用里
面要了解的，求出来应该是这样的
s[3]!=s[2],所以j=next[j],j=1
s[3]!=s[1],所以j=next[j],j=0
s[3]!=s[0],所以j=next[j],j=-1
满足j=-1，i=4,j=0,next[4]=0
下标 0 1 2 3 4
S2： a a a s
next： -1 0 1 2 0
下面是一个例题
Oulipo
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3459 Accepted Submission(s): 1351
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.
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.
3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN
1 3 0
题意是：给两个串，找出第一个在第二个里面能匹配处几个
#include <iostream>
#include <cstdio>
using namespace std;
char s1[1111111],s2[11111];
int next[11111],sum;
void getnext(char s[],int l)
//求next数组
{
int i=0,j=-1;next[i]=j;
while(i<l)
if(j==-1||s[i]==s[j])next[++i]=++j;
else j=next[j];
}
void KMP(int l1,int l2)
//匹配
{
int i=0,j=0;
while(i<l1)
{
if(j==-1||s1[i]==s2[j])i++,j++;
else j=next[j];
if(j==l2) //当匹配完成一个
{
sum++;
j=next[j]; //j跳到next
}
}
}
int main (void)
{
int n,l1,l2;
scanf("%d%*c",&n);
while(n--)
{
gets(s2);
gets(s1);
l1=strlen(s1);
l2=strlen(s2);
getnext(s2,l2);
sum=0;
KMP(l1,l2);
printf("%d\n",sum);
}
return 0;
}