给两个字符串，一个匹配串，一个主串，我们要在主串中找到第一个匹配串，并全部返回 eg: p="aba"; s="bbabaca"; 那么返回的就是第一个找到的匹配串的下标 返回2; 这里最容易想到的就是暴力匹配了,挨个，依次匹配。
核心代码:
for(int i = 1; i <= n; i++) { bool flag = true; for(int j = 1; j <= m；j++) { if(s[i+j-1] != p[j]) { flag = false; break; } } }
但这样的时间复杂度太高了，两层for循环，直接O(n*m)了,那么我们应该如何去优化呢，我们可以利用已知的信息来减少匹配次数，这就是kmp算法了
先给出kmp匹配的代码：
for(int i=1,j=0;i<=m;i++) { while(j&&b[j+1]!=a[i]) j=ne[j]; if(b[j+1]==a[i]) j++; if(j==n) { printf("%d ",i-n); j=ne[j]; } }
i是指向字符串S的，j是指向字符串P的
ne数组存的就是匹配码
这里先给出ABCDABD的匹配码0 0 0 0 1 2 0
对于图中蓝色框框都是已经匹配成功的信息，但红色框框匹配不成功，那么我们可以利用字符串P的匹配码来减少匹配，ne[j]=1;
下次匹配的时候直接从s[1+1]开始(这里的数组下标从1开始),但AC和AB又不匹配了，ne1=0,下次从s1开始匹配
最后匹配成功。
那么如何获得这个ne数组呢?
先给出匹配代码
for(int i=2,j=0;i<=n;i++) { while(j&&b[i]!=b[j+1])j=ne[j];//退而求其次重新匹配 if(b[i]==b[j+1])j++; ne[i]=j; }
这就相当于找对称字符的最长长度了
比如ababf这个字符串
我们将其拆分为
a
ab
aba
abab
ababf
对于a没有对称的字符，所以匹配码是0
ab也没有，匹配码是0
aba有，a和a，匹配码是1
abab也有，ab和ab，匹配码是2
ababf没有，匹配码是0
对于aba和abab，在我们已经知道aba已经对称的情况下，我们只需要确定这两个b是否匹配就行了,所以可以利用上一次匹配的信息，a已经匹配了,所以直接找b即可，匹配规则为下图红字部分
匹配规则样例枚举:
