KMP算法

第一种形式（数据结构严蔚敏版）

（字符串下标均从1开始）
先上代码：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int Next[100];
char S[100],T[100];
vector<int> ans;

int main()
{
    int n,m;
    cin>>n>>m;
    cin>>S+1>>T+1;

    //求Next数组
    int i = 1,j = 0;
    Next[1] = 0;
    while(i<=m)
    {
        if(j==0 || T[i] == T[j])
        {
            ++i,++j;
            Next[i] = j;
        }
        else
            j = Next[j];
    }


    /*
    for(int i = 1 ; i<=m ; i++)
        cout<<Next[i]<<" ";
    cout<<endl;
    */


    //主串与模式串开始匹配
    cout<<endl;
    i = 1,j = 1;
    while(i<=n)
    {
        if(j==0 || T[j] == S[i] && i+1<=n)
        {
            ++i,++j;
        }
        else
            j = Next[j];
        if(j==m)
        {
            ans.push_back(i-m+1);
            j = Next[j];
        }
    }

    int k = 0;
    while(k<ans.size())
    {
        cout<<ans[k++]<<" ";
    }

    return 0;
}

思路

在该程序中，主串的 i 与 j 同时从1开始遍历，j 等于 0 的情况表示需要模板串从头开始与主串匹配，j 不等于 0 时则 i 与 j 同时遍历并判断是否匹配，若失配，i 固定不回溯，模板串向前移动（ j = Next[ j ];）重复此过程，当 j 等于 模板串的长度时，说明在主串中存在此模板串，记录位置，模板串继续移动（ j = Next[ j ]; ) ，继续匹配。

第二种形式

上代码：

#include <iostream>

using namespace std;

const int N = 10010,M = 100010;

//p为模板串，s为主串
int n,m;
char p[N],s[M];
int Next[N];

int main()
{
   cin>>n>>p+1>>m>>s+1;

   Next[1] = 0;
   for(int i = 2,j = 0; i<=n ; i++)
   {
       while(j && p[i] != p[j+1]) j = Next[j];
       if(p[i] == p[j+1]) ++j;
       Next[i] = j;
   }

   /*
   for(int i = 1;i<=n;i++)
       cout<<Next[i]<<" ";
   cout<<endl;
   */

   for(int i = 1,j = 0; i<=m ; i++)
   {
       while(j && s[i]!=p[j+1]) j = Next[j];
       if(s[i] == p[j+1]) ++j;

       if(j == n)
       {
           cout<<i-n<<" ";
           j = Next[j];
       }
   }
   return 0;
}

思路

此代码与第一种形式的区别就在于求Next数组上，第一种是忽略当前位置，再当前位置前的串中求最长相同前缀后缀，将此长度+1并记录到Next数组中，因为在第一个代码中，i 与 j 都是从1开始遍历，当 j = Next[ j ] 后，直接将 i 与 j对比，而第二种形式种，求Next数组时，是观察包括当前位置的串种最长的相同前缀后缀，并直接记录在Next数组种，因为第二种代码中，i 从1开始，j 从0开始，每次对比的是 i 与 j + 1；所以当在匹配过程中发生失配时，j = Next[ j ] 实际是当前位置（i 或 j+1）的前一个位置的最长相同前缀后缀，j + 1 后 与 i 对比，实际上与第一种形式相同，但我认为这是两种不同的记录方式。

看完KMP算法，真的是敬佩三位科学家，另外，在学习过程中也遇到了很多困难，目前，对该算法的理解也只是很片面，浅显，继续努力！！！

---

更新一道例题，来源leetcode181场周赛

5367. 最长快乐前缀

「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。

输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。

输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

输入：s = "a"
输出：""

对该字符串求next数组，然后对按next[s.size()]更新答案即可

const int N = 1e5+100;
int ne[N];
class Solution {
public:
    //求next数组
    void KMP(string s)
    {
        string t = " " + s; 
        int n = t.size();   //下标从1开始
        ne[1] = 0;
        for(int i = 2,j = 0; i<=n; i++)
        {
            while(j && t[i] != t[j+1]) j = ne[j];
            if(t[i] == t[j+1]) ++j;
            ne[i] = j;
        }
    }
    string longestPrefix(string s) {
        KMP(s);
        int n = s.size();
        
        string ans = "";
        for(int i = 0; i<ne[n]; i++) ans += s[i];
        return ans;
    }
};