洛谷 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;
}