KMP

KMP主要应用在字符串匹配上。KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

思路：

• 1、首先主串和模式串逐位比较, 如果匹配, 两个指针同时加1.

• • 假设主串当前指针是 j , 模式串当前比较指针是i

• 2、而如果当前位置i 和 j 不匹配时, 模式串的比较指针i回退到模式串[0, i-1]之间的最长公共前后缀的长度的那个位置(即指向最长前缀的下一位), 此时再与主串的当前位置j继续进行比较. 如果还是不匹配, 重复2的过程. 直到回退到 i 和 j 匹配为止 或者 模式串比较指针i回退到了起始位置0.

• 3、 发生不匹配后, 经过模式串指针的回退, 此时 主串和模式串又可以愉快的进行逐位的比较了, 匹配就走1 过程. 不匹配就走2 的过程. 如果模式串比较指针 j 匹配到了结尾代表匹配成功.

next数组：

每个位置的最长公共前后缀的长度

代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;

char s[M], p[N];
int ne[N];  // 不取next，防止与std::next冲突

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;  // +1是因为主串i从1开始取，方便理解
    
    // 求next[]数组
    for (int i = 2, j = 0; i <= n; ++i) {  // i从2开始是因为ne[1]代表模式串第1个匹配失败，j就得从0重新开始
        while (j && p[i] != p[j + 1])   j = ne[j];  // 匹配失败，回退
        if (p[i] == p[j + 1])   ++j;  // 回退之后匹配主串当前字符，继续推进主串，成功则推进模式串
        ne[i] = j; // 更新next数组
    }
    
    // 匹配操作
    for (int i = 1, j = 0; i <= m; ++i) {  // 这里j代表当前匹配失败的前一位，
     // i从1开始是因为与j+1对应比较好理解，此时不匹配时，ne的下标为j
        while (j && s[i] != p[j + 1])   j = ne[j];  // 匹配失败，回退
        if (s[i] == p[j + 1])   ++j;  // 回退之后匹配主串当前字符，继续推进主串，成功则推进模式串
        if(j == n) {  // 模式串全部匹配成功
            cout << i - n << ' ';
            j = ne[j];  // 重新开始匹配
        }
    }
    
    return 0;
}

代码随想录里的代码：

void getNext(int* next, const string& s) {
    int j = 0;
    next[0] = 0;
    for(int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
            j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}
int strStr(string haystack, string needle) {
    if (needle.size() == 0) {
        return 0;
    }
    int next[needle.size()];
    getNext(next, needle);
    int j = 0;
    for (int i = 0; i < haystack.size(); i++) {
        while(j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == needle.size() ) {
            return (i - needle.size() + 1);
        }
    }
    return -1;
}