KMP：失配的时候，i 一步都不用退

// 朴素匹配：把模式串挨个位置对一遍 —— O(nm)
//
// 它是这道题最直白的翻译：文本串的每一个位置都试一次，从那儿开始逐字符比。
// ★ 而这一章第 4 步会证明一件反直觉的事：**在随机数据上它一点都不慢**
//   （每个位置平均比不到 1.1 次就失配了）。想看到它的真面目，得自己造数据。
//
// 它同时是对拍的标准答案：思路和 KMP 完全不同 —— 它对「已经匹配过的那一段」
// 没有任何记忆，失配了就把 i 退回去从头再来。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();

    vector<int> pos;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && t[i + j] == p[j]) j++;
        if (j == m) pos.push_back(i);
    }

    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';

    // 第二行：p 的 next 数组。⚠ 这一份用**定义**直接算（枚举所有可能的长度），
    // 和 fast.cpp 那个 O(m) 的递推是两条完全不同的路 —— 于是它们能互相对拍。
    for (int i = 0; i < m; i++) {
        int best = 0;
        for (int len = i; len >= 1; len--) {                 // 从长到短试
            if (p.compare(0, len, p, i + 1 - len, len) == 0) { best = len; break; }
        }
        cout << best << (i + 1 == m ? '\n' : ' ');
    }
    return 0;
}

// 换一把尺子：数「字符比较」做了多少次
//
// 这一章的秒表在小数据上完全没用（都是 0.00 秒），而**比较次数**是能数出来的、
// 换台机器也不变的东西。两种做法各放一个计数器，数的是同一个动作：
//     **拿文本里的一个字符和模式里的一个字符比一次。**
//
// ⚠ 还多数了一个：KMP 里 j 一共**回退**了多少次 —— 这是理解「为什么是 O(n+m)」的关键，
//   因为 j 每次 +1 最多 n 次，而每次回退至少让 j 减一，所以回退总数也不超过 n。
//
// 用法：./count < 输入      （和主程序一样的输入：第一行文本，第二行模式）
//       ./count csv < 输入  只打 `键,值`，给 check:viz 用

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();

    /* ① 朴素匹配 */
    long long cmpBrute = 0;
    long long hitBrute = 0;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m) { cmpBrute++; if (t[i + j] != p[j]) break; j++; }
        if (j == m) hitBrute++;
    }

    /* ② KMP（含算 next 的那一趟） */
    long long cmpKmp = 0, back = 0;
    vector<int> nxt(m, 0);
    for (int i = 1; i < m; i++) {
        int j = nxt[i - 1];
        while (j > 0) { cmpKmp++; if (p[i] == p[j]) break; j = nxt[j - 1]; back++; }
        if (j == 0) { cmpKmp++; }
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    long long hitKmp = 0;
    {
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0) { cmpKmp++; if (t[i] == p[j]) break; j = nxt[j - 1]; back++; }
            if (j == 0) { cmpKmp++; }
            if (t[i] == p[j]) j++;
            if (j == m) { hitKmp++; j = nxt[j - 1]; back++; }
        }
    }

    if (csv) {
        printf("n,%d\nm,%d\nbrute,%lld\nkmp,%lld\nback,%lld\nhit,%lld\nsame,%d\n",
               n, m, cmpBrute, cmpKmp, back, hitBrute, hitBrute == hitKmp ? 1 : 0);
        return 0;
    }
    printf("文本 %d 个字符，模式 %d 个字符，出现 %lld 次\n\n", n, m, hitBrute);
    printf("  朴素匹配   比较 %12lld 次   （理论上界 n*m = %lld）\n", cmpBrute, (long long)n * m);
    printf("  KMP        比较 %12lld 次   （其中 j 回退了 %lld 次）\n", cmpKmp, back);
    printf("\n  ★ 朴素 / KMP = %.1f 倍\n", cmpKmp ? (double)cmpBrute / cmpKmp : 0.0);
    printf("  ⚠ 两种做法找到的出现次数%s\n", hitBrute == hitKmp ? "一样（这一行是防作弊的）" : "居然不一样，有 bug");
    return 0;
}

// 正解：KMP，O(n + m)
//
// ★★ 全书的 next 约定（第三节写着，别换）：
//        nxt[i] = 「p[0..i] 这个前缀里，最长的、既是真前缀又是真后缀的那一段有多长」
//   · 长度语义（不是「指针该退到哪」那一派）· 0 基下标 · nxt[0] 恒为 0。
//   ⚠ 网上的模板两派都有（另一派把 next 往右挪一位、或者拿 −1 当哨兵），混着抄必然错。
//
// 关键的一步只有一句话：**失配时 i 一步都不退**。
//   已经匹配上的那一段 p[0..j-1] 是知道自己该退到哪的 —— 退到它的最长 border，
//   也就是 j = nxt[j-1]。因为那一段的后缀 = 前缀，所以「前面那截已经对上了」这件事不用重新验。
//
// ⚠ 算 nxt 的那个循环，本身就是「p 和自己匹配」—— 同一套回退逻辑用了两遍。
//   这一句说不透，后面就只能背代码了。

#include <bits/stdc++.h>
using namespace std;

/** nxt[i] = p[0..i] 的最长 border 长度 */
vector<int> buildNext(const string& p) {
    int m = (int)p.size();
    vector<int> nxt(m, 0);
    for (int i = 1; i < m; i++) {
        int j = nxt[i - 1];                       // 上一位的 border 长度，也是「下一个要比的位置」
        while (j > 0 && p[i] != p[j]) j = nxt[j - 1];   // 对不上就退到更短的 border
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();
    vector<int> nxt = buildNext(p);

    vector<int> pos;
    int j = 0;                                    // 当前已经匹配上的长度
    for (int i = 0; i < n; i++) {                 // ★ i 只往前走，一步都不退
        while (j > 0 && t[i] != p[j]) j = nxt[j - 1];
        if (t[i] == p[j]) j++;
        if (j == m) {
            pos.push_back(i - m + 1);
            j = nxt[j - 1];                       // ⚠ 找到一个之后要继续，允许**重叠**的下一次出现
        }
    }

    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';
    for (int i = 0; i < m; i++) cout << nxt[i] << (i + 1 == m ? '\n' : ' ');
    return 0;
}

// 正解：KMP，O(n + m)
//
// ★★ 全书的 next 约定（第三节写着，别换）：
//        nxt[i] = 「p[0..i] 这个前缀里，最长的、既是真前缀又是真后缀的那一段有多长」
//   · 长度语义（不是「指针该退到哪」那一派）· 0 基下标 · nxt[0] 恒为 0。
//   ⚠ 网上的模板两派都有（另一派把 next 往右挪一位、或者拿 −1 当哨兵），混着抄必然错。
//
// 关键的一步只有一句话：**失配时 i 一步都不退**。
//   已经匹配上的那一段 p[0..j-1] 是知道自己该退到哪的 —— 退到它的最长 border，
//   也就是 j = nxt[j-1]。因为那一段的后缀 = 前缀，所以「前面那截已经对上了」这件事不用重新验。
//
// ⚠ 算 nxt 的那个循环，本身就是「p 和自己匹配」—— 同一套回退逻辑用了两遍。
//   这一句说不透，后面就只能背代码了。

#include <bits/stdc++.h>
using namespace std;

/** nxt[i] = p[0..i] 的最长 border 长度 */
vector<int> buildNext(const string& p) {
    int m = (int)p.size();
    vector<int> nxt(m, 0);
    for (int i = 1; i < m; i++) {
        int j = nxt[i - 1];                       // 上一位的 border 长度，也是「下一个要比的位置」
        while (j > 0 && p[i] != p[j]) j = nxt[j - 1];   // 对不上就退到更短的 border
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();
    vector<int> nxt = buildNext(p);

    vector<int> pos;
    int j = 0;                                    // 当前已经匹配上的长度
    for (int i = 0; i < n; i++) {                 // ★ i 只往前走，一步都不退
        while (j > 0 && t[i] != p[j]) j = nxt[j - 1];
        if (t[i] == p[j]) j++;
        if (j == m) {
            pos.push_back(i - m + 1);
            j = nxt[j - 1];                       // ⚠ 找到一个之后要继续，允许**重叠**的下一次出现
        }
    }

    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';
    for (int i = 0; i < m; i++) cout << nxt[i] << (i + 1 == m ? '\n' : ' ');
    return 0;
}