字符串匹配kmp c++

KMP算法是一种字符串匹配算法，可以在O(n+m)的时间复杂度内解决字符串匹配问题。其基本思想是利用已知信息避免重复匹配。

具体实现步骤如下：
1. 预处理模式串，得到next数组，next[i]表示模式串中以i结尾的前缀和后缀的最长公共部分长度。
2. 在文本串中匹配模式串，当出现不匹配时，利用next数组将模式串右移一定位数，继续匹配。

C++代码实现如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;

char s[N], p[N];
int ne[N];

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

    int n = strlen(s + 1), m = strlen(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)
        {
            cout << i - m + 1 << ' ';
            j = ne[j];
        }
    }

    return 0;
}