数据结构——KMP

KMP算法

KMP是一个说复杂也算复杂、说简单也的确简单的算法。网上的介绍和详解已经很多很好了(AcWing 831. KMP字符串 - AcWing)，这里只说一下自己的理解。
核心思想：在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。

1.自己的理解

1. 感觉这个算法最主要的地方就是构造next数组，当然这个next也有一种go_back数组的感觉在里面

   这个算法最主要要解决的问题就是——字符串（也叫主串）中的模式（pattern）定位问题。也就是在一个字符串string中寻找关键字（符串）pattern，并求得其出现的具体位置。

2. i表示一个字符串中的某一个位置，j表示一个pattern中的某一个位置，若pattern中的$[0, x]$和$[y,j]$是相同的一段（即pattern中的末尾一段和从开头开始的某一段相同），则当string中从某个位置开始的到i能完全匹配pattern中的$[0, j]$，但string[ i + 1 ]与pattern[ j + 1 ]不匹配，则可尝试判断string[i + 1]与pattern[ x + 1 ]是否匹配

2.算法模板

// s[]是长文本string，p[]是模式串pattern，n是s的长度，m是p的长度
//序号从1开始

//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m) //满足匹配条件
    {
        // 匹配成功后的具体操作
        printf("%d ", i - m + 1); //输出以1开始的匹配子串的首字母下标
        j = ne[j];//再次从pattern中的某个点开始匹配
    }
}