【算法】KMP算法代码

问题：在一个字串中是否出现过另一个字串。

KMP算法的核心是找最长公共前后缀，两个字符串比较到第i个字符串时不相等了，那么模式串指针将会移动到该不相等字符的前面子字符串的最长公共前缀子串的后一个字符。

例如：

待匹配字符串：S=abdabababac
和模式字符串：P=abdabc

当两个字符串从头进行比较时，比较到下标为5的位置时S[i]='a'与P[j]='c'不相等，此时应该移动模式串指针j到c的前面子符串abdab的最长公共前后缀子串(abdab的最长公共前后缀为ab)的后一个字符P[3]='d'处进行下面的比较。

前缀表：表示模式串前i个子串的最长公共前后缀的长度，例如aabaaf，pre[0]=0，pre[1]=1，pre[2]=0，pre[3]=1，pre[4]=2，pre[5]=0。

next数组可以是前缀表，一般都是前缀表统一减一。

#include <iostream>

#define N 100010
#define M 1000010

using namespace std;

int main()
{
    int n, m;
    char P[N], S[M];
    int next[N];
    next[0] = -1;
    
    cin >> n >> P >> m >> S ;
    
    // 计算next数组
    // next[i] 表示 i（包括i）之前最长相等的前后缀长度-1（其实就是j）
    // j指向前缀起始位置，i指向后缀起始位置
    // aabaaf
    // aabaaf
    for (int i = 1, j = -1; i < n; i ++ )
    {
        while (j != -1 && P[i] != P[j + 1])
            j = next[j]; // 向前回退
        if (P[i] == P[j + 1])
            j++;
        next[i] = j; 
        // next[0]=-1
        // i=1 j=1 next[1]=0
        // i=2 j=-1 next[2]=-1
        // i=3 j=
    }
    
    // 匹配
    for (int i = 0, j = -1; i < m; i ++)
    {
        while (j!=-1 && S[i] != P[j + 1])
            j = next[j];
        if (S[i] == P[j + 1])
            j++;
        if (j == n-1)
        {
            cout << i - n + 1 << " ";
            j = next[j];
        }
    }

    // return 0;
}

例题：https://leetcode-cn.com/problems/implement-strstr/

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle == "") return 0;
        int next[50010];
        next[0] = -1;
        for (int i = 1, j = -1; i < needle.length(); i ++) {
            while (j != -1 && needle[i] != needle[j + 1]) {
                j = next[j];
            }
            if (needle[i] == needle[j + 1]) {
                j ++;
            }
            next[i] = j;
        }

        for (int i = 0, j = -1; i < haystack.length(); i ++) {
            while (j != -1 && haystack[i] != needle[j + 1]) {
                j = next[j];
            }
            if (haystack[i] == needle[j + 1]) {
                j ++;
            }
            if (j == needle.length() - 1) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }
};

参考资料
https://www.bilibili.com/video/BV1PD4y1o7nd
https://www.acwing.com/problem/content/description/833/
https://www.acwing.com/video/259/