初学KMP，除了一脸懵，又是看别人题解的一天

KMP核心思想

一.几个概念

1.s[]:模式串，长的串
2.p[]:匹配串，短的串
3.前缀：除了最后一个字符以外的，一个字符全部的头部组合
4.后缀：除了第一个字符以外的，一个字符串的全部尾部组合
5.部分匹配值：前缀集合和后缀集合共有的最长的字符串的长度
6.next[]:部分匹配值表，一个下标对应着一个匹配值

二.核心思想

每次失配时，不是把p串向后移动一位，而是把p串移动到下一次可以
和前面部分匹配的位置next[j],这样可以跳过大多数的匹配失败的步骤
每次p串移动的长度，就是通过查next表来决定的

next[]含义以及手动模拟

一.next[]含义

next[]：对于next[j] 就是模板串p[1~j]中，以1为起点的前缀，和以j为终点的后缀共有的最大长度（部分匹配值）
即 p[1~next[j]]=p[j-next[j]+1,j]

二.手动模拟

对 p = “abcab”
 p      a   b   c   a   b
下标    1   2   3   4   5
next[ ] 0   0   0   1   2

对next[ 1 ] ：前缀 = 空集                     后缀 = 空集                     next[ 1 ] = 0;
对next[ 2 ] ：前缀 = { a }                    后缀 = { b }                    next[ 2 ] = 0;
对next[ 3 ] ：前缀 = { a , ab }               后缀 = { c , bc}                next[ 3 ] = 0;
对next[ 4 ] ：前缀 = { a , ab , abc }         后缀 = { a . ca , bca }         next[ 4 ] = 1;
对next[ 5 ] ：前缀 = { a , ab , abc , abca }  后缀 = { b , ab , cab , bcab}   next[ 5 ] = 2;

作者：四谷夕雨
链接：https://www.acwing.com/solution/content/14666/

思路

一.匹配操作

• s串和p串都是从1开始的 i从1开始 j从0开始，每次是s[i]与p[j+1]比较⭐

匹配过程如图：
s[ a , b ] = p[ 1, j ] && s[ i ] != p[ j + 1 ] 此时要移动p串（不是移动1格，而是直接移动到下次能匹配的位置）
其中1串为[ 1, next[ j ] ]，3串为[ j - next[ j ] + 1 , j ]。
由匹配可知 1串等于3串，3串等于2串。
所以直接移动p串使1到3的位置即可。
这个操作可由j = next[ j ]直接完成。
如此往复下去，当 j == m时匹配成功。（此时模板串遍历完了）

• 代码实现

for(int i=1,j=0;i<n;i++)
{
    while(j && s[i]!=p[j+1]) j=ne[j];
    //如果j有对应p串元素 且 s[i]!=p[j+1] 则失配，需要移动p串
    if(s[i]==p[j+1]]) j++;
    //当前元素匹配，j移向下一位
    if(j==m)
    {
        //匹配成功
        j=ne[j];
        //继续匹配下一个子串

    }

二.求next数组

• next数组是模板串与自身匹配求出来的，思路与匹配一致

• 代码实现

next[1]=0,循环i=2开始
for(int i=2,j=0;i<n;i++)
{
    while(j && s[i]!=p[j+1]) j=ne[j];
    if(s[i]==p[j+1]) j++;
    ne[i]=j;
}

每次移动i前，将i前面已经匹配的长度，记录到next数组里

代码

#include <iostream>
using namespace std;
const int N=1e5+10,M=1e6+10;
char s[M],p[N];
int ne[N],n,m;
int main()
{
    //cin>>n>>p+1>>m>>s+1;
    cin>>n;
    for(int j=1;j<=n;j++) cin>>p[j];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>s[i];


    //构造部分匹配表ne[]
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }

    //kmp匹配
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n)
        {
            cout<<i-n<<" ";   //从1开始 i-n+1
            j=ne[j];
        }
    }
    return 0;
}