数据结构：KMP算法

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

/*
  KMP算法
  数组下标从1开始
  额外next数组，空间换时间
  时间复杂度从暴力算法O(n*m) 到 KMP算法O(m+n) = O(m)
  
  模拟：
        ababababc
        ababc
*/

#include <iostream>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M]; // p为模式串，s为子串

int ne[N]; // next数组：最长相等的前后缀，不包括整个到下标为j的数组本身

// 题目求：模式串 P 在字符串 S 中所有出现的位置的起始下标。
int main() {
    // +1代表下标从1开始的写法
    // n：模式串的长度
    // m：字符串的长度
    cin >> n >> p + 1 >> m >> s + 1;

    // 求模式串p的next数组
    // 在下标从1开始的写法中，找不到相等的前后缀，就令ne[i]=0;
    ne[1] = 0;
    for (int i = 2, j = 0; i <= n; i++) 
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1])  j++;   
        ne[i] = j;
    }

    // 寻找s中的模式串p
    // 每个匹配过程为：p的下一个字符（j+1）与s当前的字符（i） 比较
    for (int i = 1, j = 0; i <= m; i++) 
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        
        if (s[i] == p[j + 1])  j++;
            
        if (j == n) {
            cout << i - n << " "; // 下标如果从1开始数就为i-n+1
            j = ne[j];
        }
    }

    return 0;
}