洛谷 P2957 [USACO09OCT] Barn Echoes G

// P2957 [USACO09OCT] Barn Echoes G —— 正解：两个串最长的「首尾重叠」。
//
// ★ 题面把「重复部分」定义得很干净：**同时是一个串的前缀、另一个串的后缀**。
//   ⚠ 而「另一个」是双向的 —— a 的前缀配 b 的后缀，**b 的前缀配 a 的后缀也算**。
//   官方样例里两个方向都有（`yzooo` 长 5、`mo` 长 2），取大的。
//
// ★★ 这道题的规模是 **|a|, |b| ≤ 80**。
//   ⇒ 从长到短枚举重叠长度 k，直接 `substr` 比一下，最坏 80 × 80 = **6400** 次字符比较。
//   ⇒ 这一章的哈希在这儿**一分钱都不值**（见 p2957Hash.cpp 和 p2957Count.cpp）——
//     题单把它放在这儿，本来就是拿来练手的，不是因为非它不可。
//
// ⚠ 唯一那处真的会咬人的地方在**读入**：用 `cin >> s` 读，
//   `>>` 会自己跳过并吃掉所有空白 —— 而洛谷那组样例的两行**行末各带一个空格**。
//   用 `getline` 读就会把那个空格读进串里，`yzooo` 的对齐当场就没了（见 p2957Line.cpp）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    if (!(cin >> a >> b)) return 0;
    int n = (int)a.size(), m = (int)b.size();
    int ans = 0;
    for (int k = min(n, m); k >= 1; k--) {
        if (a.compare(0, k, b, m - k, k) == 0 || b.compare(0, k, a, n - k, k) == 0) { ans = k; break; }
    }
    cout << ans << '\n';
    return 0;
}

// P2957 —— ✗ 错法一：只查一个方向（只看「a 的前缀 == b 的后缀」）。
//
// ★ 题面那句「两个字符串的重复部分指的是**同时是一个字符串的前缀和另一个字符串的后缀**的字符串」
//   里，「一个」和「另一个」是**可以互换的** —— 而顺手写下去的时候只会写一半。
//
// ⚠⚠ 而**官方那组样例挡不住它**：那组数据里
//     a 的前缀 `abcxxxxabcx` 配 b 的后缀 → 11
//     b 的前缀 `abcd` 配 a 的后缀        → 4
//   ⇒ 最大值本来就在第一个方向上，只查它照样打出 11。
//   ⇒ [「这组样例在结构上问不出这个问题」](/sol/p1746/)的又一次。
//
// ★ 触发条件：**另一个方向的重叠严格更长。** 对随机数据这大约是一半一半，
//   可题面给的这组恰好不是。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    if (!(cin >> a >> b)) return 0;
    int n = (int)a.size(), m = (int)b.size();
    int ans = 0;
    for (int k = min(n, m); k >= 1; k--) {
        if (a.compare(0, k, b, m - k, k) == 0) { ans = k; break; }   // ⚠ 少了另一个方向
    }
    (void)n;
    cout << ans << '\n';
    return 0;
}

// P2957 —— ✗ 错法二：用 `getline` 读那两行。
//
// ★ 「两行字符串」这四个字看着就该用 getline，而且很多题确实必须用它
//   （[第 47 章 P1308](/sol/p1308/) 的文章里有空格，就非 getline 不可）。
//
// ⚠⚠ 可这道题的输入**行末带空白**：洛谷题面上那组样例逐字节抄下来是
//       "abcxxxxabcxabcd \nabcdxabcxxxxabcx \n"
//   —— 两行末尾**各有一个空格**。
//   getline 会把它读进串里，于是 b 的后缀不再是 `abcxxxxabcx` 而是 `bcxxxxabcx␣`
//   ⇒ 对齐当场就没了。
//
// ★ 而 `cin >> s` 天然跳过并吃掉所有空白（空格、制表、换行、`\r`）
//   ⇒ 这道题里它不是「随手选的」，是**唯一稳的那一种**。
//
// ⇒ [第 47 章那条](/sol/p1308/)反过来又成立一次：**「要不要按行读」是每道题各自的事** ——
//   那道题的空格**是内容**，这道题的空格**是垃圾**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    if (!getline(cin, a)) return 0;
    if (!getline(cin, b)) b = "";
    int n = (int)a.size(), m = (int)b.size();
    int ans = 0;
    for (int k = min(n, m); k >= 1; k--) {
        if (a.compare(0, k, b, m - k, k) == 0 || b.compare(0, k, a, n - k, k) == 0) { ans = k; break; }
    }
    cout << ans << '\n';
    return 0;
}

// P2957 —— 把「哈希在这道题上值多少」量出来。
//
// ★ 两条路都对，问题只有一句：**省下来的那点，配得上多写的那三十行吗。**
//   ① 朴素：从长到短枚举重叠长度 k，每次逐字符比 —— 最坏 2 × Σk ≈ **6400** 次字符比较（|a|=|b|=80）
//   ② 哈希：先摸完 160 个字符建前缀表，之后每个 k 都是 **O(1)**
//
// ⚠ 而这道题的上限就写在题面里：「长度为 1 到 **80** 个字母」。
//   ⇒ 这是一道三十秒的乘法题，不用跑程序也知道答案 —— 跑一遍只是为了把数写准。
//
// 用法：./p2957Count [table|csv]
#include <bits/stdc++.h>
using namespace std;

// 按显示宽度补空格：ASCII 算 1 格，汉字 / ★ 算 2 格
// ⚠ 含中文的列不能用 printf 的 %-Ns 对齐 —— 那个数的是字节，一个汉字占 3 字节却只显示 2 格。
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), ' ');
}


/** 同上，但补在左边（数字列的表头要右对齐才和 %Nlld 对得上） */
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;
}

static long long touches = 0;

/** 朴素：逐字符比，第一个不同就停 */
static int naive(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    for (int k = min(n, m); k >= 1; k--) {
        bool ok = true;
        for (int i = 0; i < k; i++) { touches++; if (a[i] != b[m - k + i]) { ok = false; break; } }
        if (ok) return k;
        ok = true;
        for (int i = 0; i < k; i++) { touches++; if (b[i] != a[n - k + i]) { ok = false; break; } }
        if (ok) return k;
    }
    return 0;
}

static const long long MOD1 = 1000000007, MOD2 = 998244353, B1 = 131, B2 = 13331;

/** 哈希：建两份前缀表（Σ|s| 次「摸字符」），之后每个 k 都是 O(1) */
static int byHash(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<long long> ha1(n + 1, 0), ha2(n + 1, 0), hb1(m + 1, 0), hb2(m + 1, 0);
    vector<long long> p1(max(n, m) + 1, 1), p2(max(n, m) + 1, 1);
    for (int i = 0; i < max(n, m); i++) { p1[i + 1] = p1[i] * B1 % MOD1; p2[i + 1] = p2[i] * B2 % MOD2; }
    for (int i = 0; i < n; i++) { touches++; long long c = (unsigned char)a[i];
        ha1[i + 1] = (ha1[i] * B1 + c) % MOD1; ha2[i + 1] = (ha2[i] * B2 + c) % MOD2; }
    for (int i = 0; i < m; i++) { touches++; long long c = (unsigned char)b[i];
        hb1[i + 1] = (hb1[i] * B1 + c) % MOD1; hb2[i + 1] = (hb2[i] * B2 + c) % MOD2; }
    auto sub = [&](const vector<long long>& h1, const vector<long long>& h2, int l, int r) {
        int len = r - l + 1;
        long long x = ((h1[r + 1] - h1[l] * p1[len]) % MOD1 + MOD1) % MOD1;
        long long y = ((h2[r + 1] - h2[l] * p2[len]) % MOD2 + MOD2) % MOD2;
        return make_pair(x, y);
    };
    for (int k = min(n, m); k >= 1; k--) {
        if (sub(ha1, ha2, 0, k - 1) == sub(hb1, hb2, m - k, m - 1)) return k;
        if (sub(hb1, hb2, 0, k - 1) == sub(ha1, ha2, n - k, n - 1)) return k;
    }
    return 0;
}

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

    /* ★ 卡朴素的形状：两串都是 79 个 'a' ＋ 一个不同的收尾字符
       ⇒ **每一个 k、每一个方向**都要一路比到最后一位才失配，而且一次都不匹配 ⇒ 2 × Σk = 6480 */
    string worstA(80, 'a'), worstB(80, 'a');
    worstA[79] = 'b'; worstB[79] = 'c';
    /* 顺手的形状：两个随机串 */
    mt19937 rng(20260909u);
    string randA(80, 'a'), randB(80, 'a');
    for (int i = 0; i < 80; i++) { randA[i] = (char)('a' + rng() % 26); randB[i] = (char)('a' + rng() % 26); }

    struct Row { const char* name; const string *x, *y; } rows[2] = {
        { "顺手：两个随机串", &randA, &randB },
        { "★ 卡它的形状：79 个 a ＋ 一个不同的收尾", &worstA, &worstB },
    };
    long long tn[2], th[2];
    int an[2], ah[2];
    for (int i = 0; i < 2; i++) {
        touches = 0; an[i] = naive(*rows[i].x, *rows[i].y); tn[i] = touches;
        touches = 0; ah[i] = byHash(*rows[i].x, *rows[i].y); th[i] = touches;
    }

    /* 秒表：单次是纳秒量级，跑 20 万遍再除 */
    const int REP = 200000;
    double msN = 0, msH = 0;
    {
        auto t0 = chrono::steady_clock::now();
        volatile int s = 0;
        for (int r = 0; r < REP; r++) s += naive(worstA, worstB);
        msN = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
        t0 = chrono::steady_clock::now();
        for (int r = 0; r < REP; r++) s += byHash(worstA, worstB);
        msH = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
        (void)s;
    }

    if (mode == "table") {
        printf("★ 两条路各摸多少个字符（|a| = |b| = 80，题面的顶格）\n\n");
        printf("    %s %s %s %s\n", padDisp("形状", 38).c_str(), padLeft("朴素", 12).c_str(), padLeft("哈希", 12).c_str(), padLeft("答案", 8).c_str());
        for (int i = 0; i < 2; i++)
            printf("    %s %12lld %12lld %8d\n", padDisp(rows[i].name, 38).c_str(), tn[i], th[i], an[i]);
        printf("\n    ⇒ 卡它的形状上哈希省了 %.1f 倍 —— 而那 %lld 次字符比较值多少时间？\n",
               (double)tn[1] / (double)th[1], tn[1]);
        printf("    单次耗时（跑 %d 遍再除）：朴素 %.2f 微秒 ／ 哈希 %.2f 微秒\n",
               REP, msN * 1000.0 / REP, msH * 1000.0 / REP);
        printf("    ⇒ ★★ 两把尺子又打架：次数省 %.1f 倍，秒表只快 %.2f 倍"
               "（建表那 160 次里每一次都带两个乘法和两个取模）\n",
               (double)tn[1] / (double)th[1], msN / msH);
        printf("    ⇒ ★★★ 而真正的结论是第三个数：两条路都是**微秒**量级，时限 1 秒 —— 余量 %.0f 万倍\n",
               1000000.0 / (msN * 1000.0 / REP) / 10000.0);
        printf("    两条路答案一致：%s\n", (an[0] == ah[0] && an[1] == ah[1]) ? "是" : "否");
    } else {
        for (int i = 0; i < 2; i++) printf("row%d,%lld %lld %d %d\n", i, tn[i], th[i], an[i], ah[i]);
        printf("saveRatio,%.1f\n", (double)tn[1] / (double)th[1]);
        printf("usN,%.2f\nusH,%.2f\ntimeRatio,%.2f\n", msN * 1000.0 / REP, msH * 1000.0 / REP, msN / msH);
    }
    return 0;
}

// P2957 数据生成器（对拍用）。用法：./p2957Gen <seed> [档位]，不给档位就是**最终档 3**。
//
// ★ 先写清楚每个错法靠什么现形：
//   ①只查一个方向  ← 要「**反方向的重叠严格更长**」。随机数据上两边都常常是 0 ⇒ 抓不到。
//   ②getline       ← 要**行末真的有空白**。⚠ 而洛谷那组官方样例的两行**末尾各有一个空格**，
//                     顺手写的生成器却不会打那个空格 ⇒ 这一格**样例比对拍还狠**。
//   ★ 试金石 p2957Zero（恒输出 0）：随机两个串的答案有九成以上就是 0 ⇒ 先让它现形。
//
// 档位：
//   0  顺手写法：两个完全随机的小写串（长 20~80）—— ★ 大多数轮次答案就是 0
//   1  ★ 真的造出一段重叠（随机挑一个方向）—— 试金石这一关先过
//   2  ★ 两个方向都造，而且**反方向更长** —— 为「只查一个方向」造的
//   3  ★★ 最终档 = 2 ＋ 行末各补一个空格 —— 为 getline 那个错法造的（照抄官方样例的样子）
#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }
static string rs(int len, int alpha) {
    string s(len, 'a');
    for (int i = 0; i < len; i++) s[i] = (char)('a' + ri(0, alpha - 1));
    return s;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int level = argc > 2 ? atoi(argv[2]) : 3;
    rng.seed(seed * 2654435761u + 999u);

    string a, b;
    if (level == 0) {
        a = rs(ri(20, 80), 26);
        b = rs(ri(20, 80), 26);
    } else if (level == 1) {
        int k = ri(1, 20);
        string ov = rs(k, 4);                       // ★ 字母表压到 4 个，重叠更容易再长出来
        if (ri(0, 1)) { a = ov + rs(ri(1, 60 - k), 4); b = rs(ri(1, 60 - k), 4) + ov; }
        else          { b = ov + rs(ri(1, 60 - k), 4); a = rs(ri(1, 60 - k), 4) + ov; }
    } else {
        int kf = ri(1, 8), kb = ri(kf + 1, kf + 12);    // ★ 反方向那一段严格更长
        string f = rs(kf, 3), g = rs(kb, 3);
        a = f + rs(ri(1, 30), 3) + g;                   // a 的前缀是 f、后缀是 g
        b = g + rs(ri(1, 30), 3) + f;                   // b 的前缀是 g、后缀是 f
        if ((int)a.size() > 80) a.resize(80);
        if ((int)b.size() > 80) b.resize(80);
    }
    if (level == 3) printf("%s \n%s \n", a.c_str(), b.c_str());   // ⚠ 照抄官方样例：行末各一个空格
    else printf("%s\n%s\n", a.c_str(), b.c_str());
    return 0;
}