洛谷 P3375 【模板】KMP

// P3375【模板】KMP —— 正解：KMP ＋ 自己写输出缓冲
//
// ★★ 这道题就是[第 48 章正文](/ch/48-kmp/)那道题的原题，**可它的约定和本书不一样**，
//   三处都要对一遍（题单注解点的就是这件事）：
//   ① 出现位置是 **1 基**（题面：「其出现位置为 l」，样例里 ABA 在 ABABABC 中是 1 和 3）——
//      本书正文一律 0 基 ⇒ 照抄要 **+1**（见 p3375Base.cpp）；
//   ② 第二行要的是「s2 的**每个前缀**的最长 border 长度」，一共 |s2| 个数
//      —— 恰好就是 0 基 nxt[0..m-1]，⚠ 但错位一格是最容易犯的（见 p3375Border.cpp）；
//   ③ 位置**按从小到大、一行一个**输出，不输出个数 —— 和正文那种「先打次数再打一行」完全不同。
//
// ⚠⚠ 而这道题真正的新关卡，正文一次都没量过：**输出**。
//   顶格 s1 = 10⁶ 个 A、s2 = 一个 A ⇒ **10⁶ 行位置，约 6.9 MB**（见 p3375Out.cpp）。
//   ⇒ `cout << x << endl` 会 flush 一百万次，当场 TLE（见 p3375Endl.cpp）。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static char s1[MAXN], s2[MAXN];
static int nxt[MAXN];

static char obuf[1 << 22];                 // 4 MiB 输出缓冲：顶格输出约 6.9 MB，分两次冲出去
static int opos = 0;
static inline void flushOut() { fwrite(obuf, 1, (size_t)opos, stdout); opos = 0; }
static inline void putc_(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }
static inline void writeInt(int x, char tail) {
    if (opos + 14 > (int)sizeof(obuf)) flushOut();
    if (!x) obuf[opos++] = '0';
    else { char t[12]; int k = 0; while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
           while (k) obuf[opos++] = t[--k]; }
    putc_(tail);
}

int main() {
    if (scanf("%s%s", s1, s2) != 2) return 0;
    int n = (int)strlen(s1), m = (int)strlen(s2);

    /* nxt[i] = s2[0..i] 的最长 border 长度（0 基）—— 正文第 5 步那五行 */
    nxt[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && s2[i] != s2[j]) j = nxt[j - 1];
        if (s2[i] == s2[j]) j++;
        nxt[i] = j;
    }
    /* 匹配：i 一步都不退 */
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && s1[i] != s2[j]) j = nxt[j - 1];
        if (s1[i] == s2[j]) j++;
        if (j == m) {
            writeInt(i - m + 2, '\n');     // ★ +1 变 1 基，再 −m+1 回到起点 ⇒ i-m+2
            j = nxt[j - 1];                // ⚠ 不能归零，否则漏掉重叠出现
        }
    }
    for (int i = 0; i < m; i++) writeInt(nxt[i], i + 1 == m ? '\n' : ' ');
    flushOut();
    return 0;
}

// P3375 ✗ 错法一：位置照抄本书的 0 基，忘了题面是 1 基
//
// ⚠ 这是「把本书的写法搬到真题上」最典型的一跤：正文里位置一律从 0 数
//   （第 47 章 P1308 也是「位置从 0 开始」），而这道题的题面写的是
//   「若 s1 的区间 [l, r] 子串与 s2 完全相同……其出现位置为 l」—— 官方样例是 1 和 3。
// ★ 触发条件干净得可以写成一句话：**只要 s2 在 s1 里出现过至少一次**。
//   ⇒ 一次都没出现时它和正解逐字节相同（那一档是能证的 0）。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static char s1[MAXN], s2[MAXN];
static int nxt[MAXN];

int main() {
    if (scanf("%s%s", s1, s2) != 2) return 0;
    int n = (int)strlen(s1), m = (int)strlen(s2);
    nxt[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && s2[i] != s2[j]) j = nxt[j - 1];
        if (s2[i] == s2[j]) j++;
        nxt[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && s1[i] != s2[j]) j = nxt[j - 1];
        if (s1[i] == s2[j]) j++;
        if (j == m) { printf("%d\n", i - m + 1); j = nxt[j - 1]; }   // ⚠ 少了那个 +1
    }
    for (int i = 0; i < m; i++) printf("%d%c", nxt[i], i + 1 == m ? '\n' : ' ');
    return 0;
}

// P3375 —— 「输出」那一关到底值多少：五种打法，同一份顶格数据各跑一遍。
//   ./p3375Out <打法> <输出文件>      打法 ∈ endl / nl / nosync / printf / buf
//   报告打在标准输出上，**正文那 6.9 MB 写进 <输出文件>**。
//
// ⚠⚠ 为什么一定要写进**文件**，而不是让它打到管道里（2026-09-07 在 [P1308](/sol/p1308/) 上撞出来的）：
//   管道那一头是谁、读得多快，**会被一起量进来**。评测机做的是「stdout 重定向到一个文件」，
//   所以这里也用 `freopen`，量完再 `dup2` 把 fd 1 换回来打报告。
//   ⇒ ★★ **量什么都要先问一句「这个数里有没有别人的份」。**
//
// ★ 顶格形状挑的是「输出最多」的那一种：s1 = 10⁶ 个 A、s2 = 一个 A
//   ⇒ **每一个位置都命中**，要打 10⁶ 行。
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

static const int N = 1000000;
static vector<int> pos;                     // 所有命中位置（1 基）
static char obuf[1 << 22];
static int opos = 0;
static inline void flushOut() { fwrite(obuf, 1, (size_t)opos, stdout); opos = 0; }
static inline void writeInt(int x) {
    if (opos + 14 > (int)sizeof(obuf)) flushOut();
    if (!x) obuf[opos++] = '0';
    else { char t[12]; int k = 0; while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
           while (k) obuf[opos++] = t[--k]; }
    obuf[opos++] = '\n';
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "buf";
    const char* out = argc > 2 ? argv[2] : "/dev/null";

    /* 顶格：s1 全是 A、s2 只有一个 A ⇒ 命中 10⁶ 次（KMP 那部分这里不是重点，直接列出位置）*/
    pos.reserve(N);
    for (int i = 1; i <= N; i++) pos.push_back(i);

    int saved = dup(1);
    if (!freopen(out, "w", stdout)) return 1;
    auto t0 = chrono::steady_clock::now();
    if (mode == "endl") {
        for (int p : pos) cout << p << endl;                 // ⚠ 每行 flush
    } else if (mode == "nl") {
        for (int p : pos) cout << p << '\n';
    } else if (mode == "nosync") {
        ios::sync_with_stdio(false);
        cout.tie(nullptr);
        for (int p : pos) cout << p << '\n';
    } else if (mode == "printf") {
        for (int p : pos) printf("%d\n", p);
    } else {
        for (int p : pos) writeInt(p);
        flushOut();
    }
    cout.flush();
    fflush(stdout);
    auto t1 = chrono::steady_clock::now();
    double ms = chrono::duration<double, milli>(t1 - t0).count();
    long long bytes = ftell(stdout);
    dup2(saved, 1);
    close(saved);
    clearerr(stdout);

    printf("%s,%.1f,%lld\n", mode.c_str(), ms, bytes);
    return 0;
}

// P3375 的生成器：./p3375Gen 种子 [档位]
//
// ★ 三个待测版本各靠什么现形：
//   · p3375Base（位置忘了 +1）  → **s2 在 s1 里至少出现一次**；
//   · p3375Border（border 行右移一格）→ **移位之后那一行和原来不同**；
//   · p3375Endl（用 endl 打）   → ⚠ **答案永远对，对拍原理上抓不到**（只能量时间）。
//
// 档位：
//   0  ★ 顺手写的：26 个大写字母随机，|s1| = 20~40、|s2| = 2~5
//      ⚠ 这一档多半**一次都不出现**（随机 26 个字母里撞上一个长度 3 的串，概率约 1/17576）
//   1  ⚠ 保证出现：先摇 s2，再把它塞进 s1 的随机位置（1~3 处）
//   2  ⚠ 字母表压到 2 个（A / B）⇒ border 非零、重叠出现满地都是
//   3  ★ 最终档：小字母表 ＋ 周期串（s2 = 一小段重复若干次）
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 1000003u + 20260908u);

    int alpha = (mode >= 2) ? 2 : 26;
    auto pick = [&]() { unsigned r = rng() % (unsigned)alpha; return (char)('A' + r); };

    unsigned r1 = rng() % 21u;
    int n = 20 + (int)r1;
    unsigned r2 = rng() % 4u;
    int m = 2 + (int)r2;

    string b;
    if (mode == 3) {                                   // 周期串：一小段重复若干次
        unsigned rp = rng() % 3u;
        int p = 1 + (int)rp;
        unsigned rk = rng() % 3u;
        int k = 2 + (int)rk;
        string unit;
        for (int i = 0; i < p; i++) unit.push_back(pick());
        for (int i = 0; i < k; i++) b += unit;
        m = (int)b.size();
    } else {
        for (int i = 0; i < m; i++) b.push_back(pick());
    }

    string a;
    for (int i = 0; i < n; i++) a.push_back(pick());
    if (mode >= 1) {                                   // 保证出现：塞 1~3 处
        unsigned rc = rng() % 3u;
        int times = 1 + (int)rc;
        for (int t = 0; t < times && m <= n; t++) {
            unsigned rp = rng() % (unsigned)(n - m + 1);
            for (int k = 0; k < m; k++) a[(size_t)rp + (size_t)k] = b[(size_t)k];
        }
    }
    printf("%s\n%s\n", a.c_str(), b.c_str());
    return 0;
}

// P3375 —— 「同一道题两条路」到底差在哪儿：把 KMP 和哈希放在一起量。
//
// ★ 第一问（找出现位置）两条路都是 O(n)，比的是**常数**：
//   KMP 每个位置做一次字符比较；哈希每个位置做一次「两个 64 位数相等吗」，
//   而建表那一遍每个字符要两次乘法 + 两次取模。
//
// ★★★ 第二问（每个前缀的最长 border）才是重点：**哈希单独做不下来**。
//   三条路，都在这儿量：
//     ① KMP           —— 跳 nxt 链，均摊 O(m)
//     ② 哈希 ＋ 均摊  —— 用「nxt[i] ≤ nxt[i−1] + 1」，同样均摊 O(m)
//                        ⚠ **而那句话就是 KMP**
//     ③ 纯哈希        —— 每个前缀从长到短逐个试，O(m²)
//   ⚠⚠ 而 ③ 的最坏形状是**随机串**（nxt 几乎全 0 ⇒ 每个 i 都要试到底），
//     全 `A` 的串反而是它的最好情形 —— 和本书大多数「顶格 ≠ 最坏」正好反过来。
//
// 用法：./p3375HashCount [cnt|time|table|csv]
#include <bits/stdc++.h>
using namespace std;

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return s + string(max(0, width - disp), ' ');
}
static string padLeft(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return string(max(0, width - disp), ' ') + s;
}

typedef long long ll;
static const ll MOD1 = 1000000007, MOD2 = 998244353, B1 = 131, B2 = 13331;
static long long ops = 0;

/* ① KMP 的 nxt：数「比较了多少次字符」 */
static vector<int> kmpNxt(const string& s) {
    int m = (int)s.size();
    vector<int> nxt(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && (++ops, s[i] != s[j])) j = nxt[j - 1];
        if ((++ops, s[i] == s[j])) j++;
        nxt[i] = j;
    }
    return nxt;
}

struct H {
    vector<ll> h1, h2, p1, p2;
    void build(const string& s) {
        int n = (int)s.size();
        h1.assign(n + 1, 0); h2.assign(n + 1, 0); p1.assign(n + 1, 1); p2.assign(n + 1, 1);
        for (int i = 0; i < n; i++) {
            ll c = s[i] - 'A' + 1;
            h1[i + 1] = (h1[i] * B1 + c) % MOD1;
            h2[i + 1] = (h2[i] * B2 + c) % MOD2;
            p1[i + 1] = p1[i] * B1 % MOD1;
            p2[i + 1] = p2[i] * B2 % MOD2;
        }
    }
    bool eq(int l1, int l2, int len) const {
        ll a = ((h1[l1 + len] - h1[l1] * p1[len]) % MOD1 + MOD1) % MOD1;
        ll b = ((h1[l2 + len] - h1[l2] * p1[len]) % MOD1 + MOD1) % MOD1;
        if (a != b) return false;
        ll c = ((h2[l1 + len] - h2[l1] * p2[len]) % MOD2 + MOD2) % MOD2;
        ll d = ((h2[l2 + len] - h2[l2] * p2[len]) % MOD2 + MOD2) % MOD2;
        return c == d;
    }
};

/* ② 哈希 ＋ 均摊：数「做了多少次段比较」 */
static vector<int> hashAmort(const string& s, const H& h) {
    int m = (int)s.size();
    vector<int> nxt(m, 0);
    for (int i = 1, k = 0; i < m; i++) {
        k++;
        while (k > 0 && (++ops, !h.eq(0, i - k + 1, k))) k--;
        nxt[i] = k;
    }
    return nxt;
}

/* ③ 纯哈希：每个前缀从长到短逐个试 */
static vector<int> hashAll(const string& s, const H& h) {
    int m = (int)s.size();
    vector<int> nxt(m, 0);
    for (int i = 1; i < m; i++) {
        int k = i;
        while (k > 0 && (++ops, !h.eq(0, i - k + 1, k))) k--;
        nxt[i] = k;
    }
    return nxt;
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    bool csv = (mode == "csv");

    /* ---------- 第二问的次数表 ---------- */
    const int MS[3] = { 500, 2000, 8000 };
    const char* SHAPE[2] = { "★ 26 个大写字母随机（nxt 几乎全 0）", "全是 A（nxt = 0,1,2,…）" };
    long long tab[2][3][3];
    int allSame = 1;
    for (int sh = 0; sh < 2; sh++)
        for (int k = 0; k < 3; k++) {
            int m = MS[k];
            string s(m, 'A');
            mt19937 rg(20260909u + sh * 13 + k);
            if (sh == 0) for (int i = 0; i < m; i++) s[i] = (char)('A' + rg() % 26);
            H h; h.build(s);
            ops = 0; vector<int> a = kmpNxt(s);      tab[sh][k][0] = ops;
            ops = 0; vector<int> b = hashAmort(s, h); tab[sh][k][1] = ops;
            ops = 0; vector<int> c = hashAll(s, h);   tab[sh][k][2] = ops;
            if (a != b || a != c) allSame = 0;
        }

    if (mode == "cnt" || mode == "table") {
        printf("★ 第二问（每个前缀的最长 border）：三条路各做多少次比较\n\n");
        for (int sh = 0; sh < 2; sh++) {
            printf("  %s\n", SHAPE[sh]);
            printf("    %-8s %s %s %s\n", "|s2|", padLeft("① KMP", 14).c_str(),
                   padLeft("② 哈希＋均摊", 16).c_str(), padLeft("③ 纯哈希 O(m²)", 18).c_str());
            for (int k = 0; k < 3; k++)
                printf("    %-8d %14lld %16lld %18lld\n", MS[k],
                       tab[sh][k][0], tab[sh][k][1], tab[sh][k][2]);
            printf("    m 每翻 4 倍，③ 这一列 ×%.1f、×%.1f\n\n",
                   (double)tab[sh][1][2] / tab[sh][0][2], (double)tab[sh][2][2] / tab[sh][1][2]);
        }
        printf("    三条路算出来的 nxt 数组完全一致：%s\n\n", allSame ? "是" : "否");
    }

    /* ---------- 顶格第一问的秒表 ---------- */
    double tKmp = 0, tHash = 0;
    long long cKmp = 0, cHash = 0;
    {
        const int N = 1000000, M = 1000;
        string s1(N, 'A'), s2(M, 'A');
        mt19937 rg(20260909u);
        for (int i = 0; i < N; i++) s1[i] = (char)('A' + rg() % 26);
        for (int i = 0; i < M; i++) s2[i] = s1[12345 + i];      // ★ 保证真的出现过一次
        double v[3];
        for (int r = 0; r < 3; r++) {
            auto t0 = chrono::steady_clock::now();
            vector<int> nxt = kmpNxt(s2);
            ops = 0;
            volatile int hit = 0;
            for (int i = 0, j = 0; i < N; i++) {
                while (j > 0 && (++ops, s1[i] != s2[j])) j = nxt[j - 1];
                if ((++ops, s1[i] == s2[j])) j++;
                if (j == M) { hit++; j = nxt[j - 1]; }
            }
            cKmp = ops;
            v[r] = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
        }
        sort(v, v + 3); tKmp = v[1];
        for (int r = 0; r < 3; r++) {
            auto t0 = chrono::steady_clock::now();
            H a, b;
            a.build(s1); b.build(s2);
            ops = 0;
            volatile int hit = 0;
            ll g1 = b.h1[M], g2 = b.h2[M];
            for (int i = 0; i + M <= N; i++) {
                ops++;
                ll x = ((a.h1[i + M] - a.h1[i] * a.p1[M]) % MOD1 + MOD1) % MOD1;
                if (x != g1) continue;
                ll y = ((a.h2[i + M] - a.h2[i] * a.p2[M]) % MOD2 + MOD2) % MOD2;
                if (y == g2) hit++;
            }
            cHash = ops;
            v[r] = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
        }
        sort(v, v + 3); tHash = v[1];
    }

    if (mode == "time" || mode == "table") {
        printf("★ 第一问（找出现位置）顶格 |s1| = 10⁶、|s2| = 10³（3 次取中位数）\n\n");
        printf("    %s %14s %16s\n", padDisp("", 20).c_str(), "比较次数", "毫秒");
        printf("    %s %14lld %14.1f ms\n", padDisp("① KMP", 20).c_str(), cKmp, tKmp);
        printf("    %s %14lld %14.1f ms\n", padDisp("② 哈希", 20).c_str(), cHash, tHash);
        printf("\n    ⇒ ★★ 两把尺子又打架：哈希的**比较次数更少**（%lld < %lld），"
               "秒表却慢 %.1f 倍\n", cHash, cKmp, tHash / tKmp);
        printf("       —— 因为哈希那 %d 个字符每一个都要两次乘法 ＋ 两次取模，而 KMP 只是比一个字节\n", 1000000);
        printf("    ⇒ 两条路都是 O(n)、都能过（时限 1 秒），可**哈希在第一问上没有任何便宜可占**\n");
        printf("    ⚠ 而单模数在这道题上撞的概率：每次提交约 (n − m + 1) / 10⁹ = %.4f%%\n",
               100.0 * (1000000 - 1000 + 1) / 1e9);
    }

    if (csv) {
        for (int sh = 0; sh < 2; sh++)
            for (int k = 0; k < 3; k++)
                printf("cnt%d_%d,%lld %lld %lld\n", sh, MS[k], tab[sh][k][0], tab[sh][k][1], tab[sh][k][2]);
        for (int sh = 0; sh < 2; sh++)
            printf("grow%d,%.1f %.1f\n", sh,
                   (double)tab[sh][1][2] / tab[sh][0][2], (double)tab[sh][2][2] / tab[sh][1][2]);
        printf("allSame,%d\ncKmp,%lld\ncHash,%lld\ntKmp,%.1f\ntHash,%.1f\n",
               allSame, cKmp, cHash, tKmp, tHash);
    }
    return 0;
}