python/TangDou/AcWing/KMP/831_1.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;  // 模板串最大长度限制
const int M = 1000010; // 模式串最大长度限制

int n;     // 短串长度
int m;     // 长串长度
int ne[N]; // next数组
char s[M]; // 长串
char p[N]; // 短串

int main() {
    cin >> n >> (p + 1) >> m >> (s + 1);
    // 一、求ne数组
    // i:当前试图进行匹配的S串字符，j+1是模板串当前试图与S串i位置进行匹配的字符
    // j:表示已匹配的长度，一直都在尝试让j+1位和i位进行匹配,退无可退，无需再退。
    // i:是从2开始的，因为ne[1]=0,表示第1个不匹配，只能重头开始，不用算
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        // 如果是匹配情况发生了，那么j移动到下一个位置
        if (p[i] == p[j + 1]) j++;
        // 记录j到ne数组中
        ne[i] = j;
    }

    // 二、匹配字符串
    // i:当前试图进行对比的S串位置
    // j:最后一个已完成匹配的P串位置，那么，当前试图与S串当前位置i进行尝试对比匹配的位置是j+1
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && s[i] != p[j + 1]) j = ne[j]; // 不行就退吧,当j==0时，表示退无可退，无需再退
        // 如果是匹配情况发生了，那么j移动到下一个位置
        if (s[i] == p[j + 1]) j++; // 匹配则指针前行，i不用++，因为它在自己的for循环中，自带++
        if (j == n) {              // 如果匹配到最大长度，说明完成了所有位置匹配
            printf("%d ", i - n);  // 输出开始匹配位置
            j = ne[j];             // 回退，尝试继续进行匹配，看看还有没有其它可以匹配的位置
        }
    }
    return 0;
}