感觉信手拈来的东西，怎么写着写着就不懂了呢？
请先看这里，大致了解该算法。
这个时间复杂度O(n+m)，网上已然有很多介绍了，不如我就贴个我的代码。。
char str[1000010],ss[10010];
int nxt[10010],str_len,ss_len;//nxt即next数组，会和next()产生歧义，就改个名字吧。。
void genNext() {
int i=0,j=-1;
for (int i=0,j=-1; i<=ss_len; i++,j++) {
nxt[i]=j;
if (j!=-1 && ss[i]==ss[j])
nxt[i]=nxt[j];
while (j!=-1 && ss[i]!=ss[j])
j=nxt[j];
}
for (int i=0;i<=strlen(ss);i++)
cout<<nxt[i]<<" ";
cout<<endl;
}
int main() {
int ans=0;
cin>>ss; //ss短
cin>>str; //str长
genNext();
for (int i=0,j=0; i<strlen(str); ) {
if (j==-1 || str[i]==ss[j])
i++,j++;
else
j=nxt[j];
if (j==strlen(ss))
ans++,j=nxt[j];
}
cout<<ans<<endl;//ans输出一共匹配到了多少次。。。
}匹配这部分很简单，就是如果匹配失败了就跳到next再尝试，再失败了再跳。
next的意义就是：如果当前ss[k]位置失败了，k往前跳到next[k]还能继续试着比一比。
关键来看genNext这段：
next的生成，就是自己的“当前串”，匹配自己的“开头串”，直到走完。
i作为进度条，会一直向前走不回头。
举例，假如现在主进度条i=11，与之匹配的 “开头串”中的p=3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a b e a b c F F a b e a b d \0
p i
相同，往下走，（i=12,p=4），相同，继续，到达i=13,p=5，不同，处理一下。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a b e a b c F F a b e a b d \0
p i
此时我们想的是，[0-5]和[8-13]匹配不上了，退而求其次看看[0-2]和[11-13]能不能匹配上呢，于是此时 set p=next[p];
于是p=2 又发现，[0-2]!=[11-13]，只好在次退而求其次set p=next[p]; 得到p=0;
p=0发现[0-0]!=[13-13]，set p=next[p];得到p=-1;
我们假定ss[-1]=*万能，这样就可以当[-1,-1]和任何一个匹配时候都可以继续下去。
此时跳过，到达i=14,游戏结束（当然也建议给\0位也求一个next，这样可以当字符串匹配完了跳回去继续找，就可以匹配无限多次了）。
于是就有了这段代码，找不到就跳，直到跳没了(p=-1，这样放弃掉ss[i]) 或者能找到(ss[0...]==ss[...i])，然后进度条+1，直接下一个：
for (int i=0,j=-1; i<=ss_len; i++,j++)
while (j!=-1 && ss[i]!=ss[j])
j=nxt[j];
（我们也可以发现：在任何时候ss[0...j-1]和ss[...i-1]都是相同的。）那么问题来了，一上来没有next[]。
所以，当我们把ss[i]和ss[p]比较时候，就把next[i]=p给存上，无论ss[i],ss[p]是不是一样的，表示的是如果在main中，这个位置失败了，就往前跳一下接着比。
可是想想next[]数组用的时候，是失败了才跳，那假如说跳之前的ss[i]和跳之后的ss[next[i]]一样，那不是跳了也失败。
所以在此加优化：
next[i]=p;
if (p!=-1 && ss[i]==ss[p]) //这个if是优化
next[i]=next[p];就是如果跳之前和之后相等，就给它指过去。
扩展
假设pattern串用ss[]表示，则在不加if优化时候，
- next[i]==p代表：对于ss[0...i-1]这个字符串，他的长度为p的prefix和suffix相同，且这个长度p是最长的串了。
- ss[0...next[p]-1]是第二长的"prefix==suffix"的串
- 由于没有if优化，除了next[0]==-1,其他的next[]都不会是-1，最次是0。
NB plus