KMP字符串

一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。 — KMP

题目描述

给定一个字符串text，以及一个子串sub，所有字符串中只包含大小写英文字母以及阿拉伯数字。

子串sub在字符串text中多次作为子串出现。

求出子串sub在字符串text中所有出现的位置的起始下标。

输入格式

第一行输入整数n，表示字符串sub的长度。

第二行输入字符串sub。

第三行输入整数m，表示字符串text的长度。

第四行输入字符串text。

输出格式

共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

\(1≤n≤10^5\)，\(1≤m≤10^6\)

可以先看灯神的讲解后，再来看代码。

#include<iostream>
using namespace std;

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

int nex[N], n, m; // nex数组，n为子串长度，m为文本长度
char text[M], sub[N]; // text为文本，sub为子串

void kmp() {
    // 计算子串的next数组
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && sub[i] != sub[j + 1]) j = nex[j]; // 当前字符不匹配，回溯
        if (sub[i] == sub[j + 1]) j++; // 当前字符匹配，前进
        nex[i] = j; // 更新next数组
    }

    // 在文本中查找子串
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && text[i] != sub[j + 1]) j = nex[j]; // 文本与子串当前字符不匹配，根据next数组回溯
        if (text[i] == sub[j + 1]) j++; // 当前字符匹配，前进
        if (j == n) { // 找到一个子串的匹配
            cout << i - n << ' '; // 输出匹配的起始位置
            j = nex[j]; // 根据next数组继续搜索可能的下一个匹配
        }
    }
}

int main() {
    cin >> n >> sub + 1 >> m >> text + 1; // 输入子串和文本，从数组的第1位开始存储字符串
    kmp(); // 执行KMP算法
    return 0;
}