#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 求模式串p的next数组（最长border）
vector<int> getNext(const string &p) {
    int n = p.size();
    vector<int> next(n + 1, 0); // next[1]~next[n] 对应长度1~n前缀
    int j = 0;
    for (int i = 2; i <= n; ++i) {
        while (j > 0 && p[i - 1] != p[j]) j = next[j];
        if (p[i - 1] == p[j]) j++;
        next[i] = j;
    }
    return next;
}

// KMP匹配，返回所有匹配起始位置（1开头）
vector<int> kmpSearch(const string &s, const string &p, const vector<int> &next) {
    vector<int> res;
    int n = s.size(), m = p.size();
    int j = 0;
    for (int i = 1; i <= n; ++i) {
        while (j > 0 && s[i - 1] != p[j]) j = next[j];
        if (s[i - 1] == p[j]) j++;
        // 完全匹配
        if (j == m) {
            res.push_back(i - m + 1); // 左端点l（1起始）
            j = next[j];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s1, s2;
    cin >> s1 >> s2;
    
    auto next = getNext(s2);
    auto pos = kmpSearch(s1, s2, next);
    
    // 输出所有匹配位置
    for (int x : pos) cout << x << '\n';
    // 输出next[1]~next[m]，空格分隔
    int m = s2.size();
    for (int i = 1; i <= m; ++i) {
        cout << next[i] << ' ';
    }
    return 0;
}

next特性：len-next[len]是最小循环节

优化失配数组

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> getNext(const string &p) {
    int n = p.size();
    vector<int> next(n + 1, 0);
    int j = 0;
    for (int i = 2; i <= n; ++i) {
        while (j > 0 && p[i - 1] != p[j]) j = next[j];
        if (p[i - 1] == p[j]) j++;
        next[i] = j;
    }
    return next;
}

// 生成nextval优化数组
vector<int> getNextVal(const string &p, const vector<int> &next) {
    int n = p.size();
    vector<int> nextval(n + 1, 0);
    nextval[1] = 0;
    for (int i = 2; i <= n; ++i) {
        int k = next[i];
        while (k > 0 && p[i - 1] == p[k]) k = next[k];
        nextval[i] = k;
    }
    return nextval;
}

// KMP匹配改用nextval
vector<int> kmpSearchVal(const string &s, const string &p, const vector<int> &nextval) {
    vector<int> res;
    int n = s.size(), m = p.size();
    int j = 0;
    for (int i = 1; i <= n; ++i) {
        while (j > 0 && s[i - 1] != p[j]) j = nextval[j];
        if (s[i - 1] == p[j]) j++;
        if (j == m) {
            res.push_back(i - m + 1);
            j = nextval[j];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s1, s2;
    cin >> s1 >> s2;
    
    auto next = getNext(s2);
    auto nextval = getNextVal(s2, next);
    auto pos = kmpSearchVal(s1, s2, nextval);
    
    for (int x : pos) cout << x << '\n';
    int m = s2.size();
    for (int i = 1; i <= m; ++i) cout << nextval[i] << ' ';
    return 0;
}

KMP 完整原理，分三层讲：问题、暴力缺陷、next 数组、匹配流程、nextval 优化

一、原始问题：字符串模式匹配

给定文本串 S（长 n）、模式串 P（长 m），找出 S 中所有 P 出现的位置。

暴力匹配缺点

两个指针 i（文本）、j（模式）：

1. 匹配相等：\(i++,j++\)
2. 失配：i 回退到 \(i-j+2\)，j 归零 最坏复杂度 \(O(nm)\)，如 S=aaaaaaa，P=aaab，大量重复比较浪费时间。

KMP 核心目标：失配时，文本指针 i 不回退，只让模式指针 j 跳到最优位置，整体线性 \(O(n+m)\)。

二、核心概念：Border（前缀函数 /next 数组）

1. 定义

对模式串前 i 个字符组成的前缀 \(P[1,i]\)：

• 真前缀：不包含最后一位；真后缀：不包含第一位；
• \(next[i]\) = 最长的长度 k，满足前 k 位 = 后 k 位（\(k<i\)），这个长度叫 Border。

例：\(P=abcab\)（长度 5） 前缀：a ab abc abca abcab 后缀：b ab cab bcab abcab 最长相等真前后缀是 ab，长度 2 → \(next[5]=2\)。

2. next 数组求解逻辑（1-based，和你板子统一）

j 记录上一个前缀的最长 border 长度：

1. \(next[1]=0\)：单个字符无真前后缀；
2. i 从 2 遍历到 m：
   • 若 \(P[i-1] \ne P[j]\)：\(j=next[j]\) 回溯，直到 \(j=0\)；
   • 匹配相等：\(j++\)；
   • \(next[i]=j\)。 全程只前进不回退，\(O(m)\) 求出 next。

3. Border 的关键作用（KMP 灵魂）

当匹配到 \(P[j]\) 和文本失配时： \(P[1,j-1]\) 是已经匹配成功的一段，不需要全部重比。 利用 \(next[j-1]=k\)：说明 \(P[1,k] = P[j-k,j-1]\)，直接把 j 跳到 k，文本指针 i 不动。

举例： \(P=abcabc\)，匹配到第 6 位失配，\(next[6]=3\)，直接让 \(j=3\)，拿 \(P[3]\) 继续和当前文本字符对比，省去从头匹配。

三、KMP 匹配主流程

设文本 S，模式 P，i 文本下标，j 模式下标：

1. 循环遍历文本每个字符 \(S[i]\)：
   • 失配且 \(j>0\)：\(j=next[j]\)；
   • 若字符相等：\(i++,j++\)；
2. 当 \(j=m\)（模式完全匹配）：
   • 记录匹配起点；
   • \(j=next[j]\) 寻找重叠匹配（比如 aaaa 中 aa 会多次匹配）。

全程 i 只增不减，总复杂度 \(O(n+m)\)。

四、nextval（优化失配数组）原理

问题：普通 next 存在无效跳转

例 \(P=aaaaa\)，\(next[4]=3\)，若 \(P[4]=P[3]='a'\)： 失配时跳到 \(j=3\)，字符还是 a，依然失配，多一次无用判断。

nextval 优化规则

对每个 i：

1. \(k=next[i]\)；
2. 若 \(P[i-1] == P[k]\)，继续令 \(k=next[k]\)，直到字符不等或 \(k=0\)；
3. \(nextval[i]=k\)。

作用：失配时一步跳到字符不同的位置，减少比较次数，卡常专用。

五、拓展：Border 衍生知识点

1. 最小循环节

字符串总长 L，最长 border \(k=next[L]\)，循环节长度 \(d=L-k\)。

• 若 \(L \% d ==0\)：整个串由 \(L/d\) 个相同子串重复；
• 否则最小循环节是自身。 例：abcabcabc，\(L=9,next[9]=6,d=3\)，可由abc重复 3 次构成。

2. 所有 Border 数量（cnt 数组，动物园题）

\(cnt[i]\) = 前缀 i 所有合法 border 的总个数 递推式：\(cnt[i] = cnt[next[i]] +1\) 含义：最长 border + 最长 border 的所有 border。

3. 不重叠 border（num 数组，NOI 动物园）

要求 \(2k \le i\)（前后缀不重叠），用双指针维护最大合法 k，\(num[i]=cnt[k]\)，最后累乘 \((num[i]+1)\) 得答案。