洛谷 P1470 [IOI 1996 / USACO2.3] 最长前缀

// P1470 最长前缀 —— 正解：一维可达性 DP，和 KMP 一点关系都没有
//
// ★★ 这道题挂在[第 48 章](/ch/48-kmp/)的题单里，题单注解写得很直白：
//   「字符串 + DP，**不用 KMP 也能过**。★ 放在这儿是想说明：不是所有字符串题都要上 KMP」。
//   ⇒ 它考的是**读入** ＋ **一句 DP**，而这两样都不需要 next 数组。
//
// ★ DP 一句话：f[k] = 「S 的前 k 个字符能被拼出来吗」
//     f[0] = true；f[k] = 存在元素 e（|e| ≤ min(10, k)）使 f[k-|e|] 且 S 的第 k-|e|..k-1 位正好是 e。
//   答案 = **最大的**满足 f[k] 的 k。
//   ⚠⚠ 注意是「最大的」而不是「第一个断点之前的」—— **f 不是单调的**
//     （P = {AA}、S = AAAA 时 f 是 F T F T）⇒ 见 p1470First.cpp。
//
// ⚠ 读入有两处，题面都明写着，而**官方样例一处都没考到**：
//   ① 元素集合「**数据可能不止一行**」，以只含一个 `.` 的行结束；
//   ② S「用**一行或者多行**的字符串来表示，**换行符并不是序列 S 的一部分**」。
//   ⇒ 一路 `cin >> tok` 读到底最省事：它天然跨行（见 p1470Line.cpp —— 那一版假设 S 只有一行）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<unordered_set<string>> byLen(11);        // 按长度分组：元素长度 ≤ 10
    string tok;
    while (cin >> tok && tok != ".") if (tok.size() <= 10) byLen[tok.size()].insert(tok);

    string s;
    while (cin >> tok) s += tok;                    // ★ 一路读到 EOF，自动跨行

    int n = (int)s.size();
    vector<char> f((size_t)n + 1, 0);
    f[0] = 1;
    int ans = 0;
    for (int k = 1; k <= n; k++) {
        for (int len = 1; len <= 10 && len <= k; len++) {
            if (!f[(size_t)(k - len)]) continue;
            if (byLen[(size_t)len].count(s.substr((size_t)(k - len), (size_t)len))) { f[(size_t)k] = 1; break; }
        }
        if (f[(size_t)k]) ans = k;                  // ⚠ 一路记最大的，不能遇到 false 就停
    }
    printf("%d\n", ans);
    return 0;
}

// P1470 ✗ 错法一：以为 S 只有一行
//
// ⚠ 题面写得很清楚：S「用**一行或者多行**的字符串来表示，每行不超过 76 个字符。
//   换行符并不是序列 S 的一部分」。
//   ⇒ 只 `getline` 一行（或者只 `cin >> s` 一次），S 就被截断在第一行末尾。
// ★ 触发条件：**S 真的跨了多行**。
// ⚠⚠ 而官方那组样例的 S **正好只有一行** ⇒ **它放过这个错法**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<unordered_set<string>> byLen(11);
    string tok;
    while (cin >> tok && tok != ".") if (tok.size() <= 10) byLen[tok.size()].insert(tok);

    string s;
    cin >> s;                                       // ⚠ 只读了一段，后面几行全丢了

    int n = (int)s.size();
    vector<char> f((size_t)n + 1, 0);
    f[0] = 1;
    int ans = 0;
    for (int k = 1; k <= n; k++) {
        for (int len = 1; len <= 10 && len <= k; len++) {
            if (!f[(size_t)(k - len)]) continue;
            if (byLen[(size_t)len].count(s.substr((size_t)(k - len), (size_t)len))) { f[(size_t)k] = 1; break; }
        }
        if (f[(size_t)k]) ans = k;
    }
    printf("%d\n", ans);
    return 0;
}

// P1470 ✗ 错法二：遇到第一个「拼不出来」就停
//
// ⚠ 这一版假设了 **f 是单调的** —— 拼不出前 k 个，就更拼不出前 k+1 个。**那是错的。**
//   最小反例只要一个元素：P = {AA}、S = AAAA ⇒ f 是 **F T F T**，答案是 4，
//   而这一版在 k = 1 就停下来，输出 0。
// ★ 触发条件：**f 中间有「洞」，而答案落在洞的后面**
//   —— 也就是「最大的 f[k]」比「第一个断点之前的 k」大。
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<unordered_set<string>> byLen(11);
    string tok;
    while (cin >> tok && tok != ".") if (tok.size() <= 10) byLen[tok.size()].insert(tok);
    string s;
    while (cin >> tok) s += tok;

    int n = (int)s.size();
    vector<char> f((size_t)n + 1, 0);
    f[0] = 1;
    int ans = 0;
    for (int k = 1; k <= n; k++) {
        for (int len = 1; len <= 10 && len <= k; len++) {
            if (!f[(size_t)(k - len)]) continue;
            if (byLen[(size_t)len].count(s.substr((size_t)(k - len), (size_t)len))) { f[(size_t)k] = 1; break; }
        }
        if (!f[(size_t)k]) break;                   // ⚠ 以为 f 是单调的
        ans = k;
    }
    printf("%d\n", ans);
    return 0;
}

// P1470 —— 「200 个元素挨个试会不会超时」这笔账。
//   ./p1470Count        人话版
//   ./p1470Count csv    给 check:viz 用
//
// ★★ 名义上界一句乘法：|S| × card(P) × |e| = 2×10⁵ × 200 × 10 = **4 × 10⁸**。
//   ⇒ 「四亿次肯定超时」是句要**乘一遍、再量一遍**才能说的话
//   （[第 41 章 P1217](/sol/p1217/)、[第 42 章 P1045](/sol/p1045/)、[第 46 章 P1582](/sol/p1582/) 都中过）。
//
// ⚠ 关键在于那两句短路：`if (len > k || !f[k-len]) continue;` 和「一撞上就 break」
//   ⇒ 真正做的比较次数**远到不了 4 亿**，而且**取决于数据形状**：
//   · 顺手造的顶格（元素随机、S 由它们拼成）—— 大部分 k 上 `f[k-len]` 是假的，一比都不用比；
//   · ★ 卡它的形状（所有元素共享前缀 `AAAAA`、唯一能匹配的那个排在最后、S 全是 A）
//     —— 每个 k 都要把 199 个元素比到第 6 个字符才失配。
#include <bits/stdc++.h>
using namespace std;

static const int NS = 200000;                       // |S| 顶格

/** 朴素版：数「字符比较」做了多少次 */
static long long naiveCmp(const vector<string>& es, const string& s) {
    int n = (int)s.size();
    vector<char> f((size_t)n + 1, 0);
    f[0] = 1;
    long long cmp = 0;
    for (int k = 1; k <= n; k++) {
        for (const string& e : es) {
            int len = (int)e.size();
            if (len > k || !f[(size_t)(k - len)]) continue;
            int t = 0;
            while (t < len && s[(size_t)(k - len + t)] == e[(size_t)t]) { cmp++; t++; }
            if (t < len) { cmp++; continue; }
            f[(size_t)k] = 1;
            break;
        }
    }
    return cmp;
}
/** 正解：数「哈希查了多少次」 */
static long long groupLookups(const vector<string>& es, const string& s) {
    vector<unordered_set<string>> byLen(11);
    for (const string& e : es) byLen[e.size()].insert(e);
    int n = (int)s.size();
    vector<char> f((size_t)n + 1, 0);
    f[0] = 1;
    long long look = 0;
    for (int k = 1; k <= n; k++)
        for (int len = 1; len <= 10 && len <= k; len++) {
            if (!f[(size_t)(k - len)]) continue;
            look++;
            if (byLen[(size_t)len].count(s.substr((size_t)(k - len), (size_t)len))) { f[(size_t)k] = 1; break; }
        }
    return look;
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";
    mt19937 rng(20260908u);

    /* ① 顺手造的顶格：200 个随机长度 10 的元素，S 由它们拼起来 */
    vector<string> esR;
    {
        set<string> u;
        while ((int)u.size() < 200) {
            string e;
            for (int i = 0; i < 10; i++) { unsigned c = rng() % 5u; e.push_back((char)('A' + c)); }
            u.insert(e);
        }
        esR.assign(u.begin(), u.end());
    }
    string sR;
    while ((int)sR.size() < NS) { unsigned r = rng() % 200u; sR += esR[r]; }
    sR.resize(NS);

    /* ② 卡它的形状：共享前缀 AAAAA、唯一能匹配的 "A" 排在最后、S 全是 A */
    vector<string> esW;
    {
        set<string> u;
        while ((int)u.size() < 199) {
            string e = "AAAAA";
            for (int i = 0; i < 5; i++) { unsigned c = rng() % 10u; e.push_back((char)('B' + c)); }
            u.insert(e);
        }
        esW.assign(u.begin(), u.end());
        esW.push_back("A");
    }
    string sW((size_t)NS, 'A');

    long long cmpR = naiveCmp(esR, sR), cmpW = naiveCmp(esW, sW);
    long long lookR = groupLookups(esR, sR), lookW = groupLookups(esW, sW);
    long long bound = (long long)NS * 200 * 10;

    if (csv) {
        printf("bound,%lld\ncmpRandom,%lld\ncmpWorst,%lld\n", bound, cmpR, cmpW);
        printf("lookRandom,%lld\nlookWorst,%lld\n", lookR, lookW);
        printf("shapeRatio,%.1f\nvsBound,%.1f\n",
               (double)cmpW / (double)cmpR, (double)bound / (double)cmpW);
        return 0;
    }
    printf("名义上界：|S| × card(P) × |e| = %d × 200 × 10 = %lld\n", NS, bound);
    printf("★ 朴素版真做的字符比较次数：\n");
    printf("   顺手造的顶格（元素随机 ＋ S 由它们拼成）：%12lld\n", cmpR);
    printf("   ★ 卡它的形状（共享前缀 ＋ 匹配的排最后）：%12lld（差 %.1f 倍）\n",
           cmpW, (double)cmpW / (double)cmpR);
    printf("   ⇒ 连最坏的那一档也只有名义上界的 1/%.1f —— 两句短路把它砍掉了\n",
           (double)bound / (double)cmpW);
    printf("★ 正解（按长度分组 ＋ 哈希）查表次数：随机 %lld，卡它的形状 %lld\n", lookR, lookW);
    return 0;
}

// P1470 的生成器：./p1470Gen 种子 [档位]
//
// ★ 三个错法各靠什么现形：
//   · p1470Line（以为 S 只有一行）→ **S 真的跨了多行**；
//   · p1470First（遇到第一个断点就停）→ **f 中间有洞，而答案落在洞后面**；
//   · p1470Zero（忘了 f[0]=true）→ **正解的答案不是 0**。
//
// 档位：
//   0  ★ 顺手写的：元素 5 个（长度 1~3）、S 单行随机 20~40 个字符
//      ⚠ 这一档 **S 只有一行** ⇒ 「以为只有一行」那个错法是**结构性的 0**
//        —— 而官方那组样例犯的是同一个毛病
//   1  ⚠ 元素长度压到 2~3（★ 长度全 ≥ 2 才容易出「洞」）、S 由元素拼成 ＋ 随机尾巴，仍是单行
//   2  ⚠ 同上，但 **S 拆成 2~4 行**（p1470Line 的专门档）
//   3  ★ 最终档：元素长度固定 2 ＋ 多行 ⇒ 洞最多
//
// ⚠ 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);

    const int ALPHA = 3;                            // A / B / C
    auto pick = [&]() { unsigned r = rng() % (unsigned)ALPHA; return (char)('A' + r); };

    int loLen = (mode == 0) ? 1 : 2;
    int hiLen = (mode == 3) ? 2 : 3;

    unsigned rc = rng() % 4u;
    int m = 3 + (int)rc;                            // 3~6 个元素
    vector<string> es;
    set<string> used;
    for (int i = 0; i < m; i++) {
        unsigned rl = rng() % (unsigned)(hiLen - loLen + 1);
        int len = loLen + (int)rl;
        string e;
        for (int k = 0; k < len; k++) e.push_back(pick());
        if (used.insert(e).second) es.push_back(e);
    }
    for (size_t i = 0; i < es.size(); i++) printf("%s%c", es[i].c_str(), i + 1 == es.size() ? '\n' : ' ');
    printf(".\n");

    string s;
    if (mode == 0) {
        unsigned rn = rng() % 21u;
        int n = 20 + (int)rn;
        for (int i = 0; i < n; i++) s.push_back(pick());
    } else {
        unsigned rk = rng() % 8u;
        int k = 5 + (int)rk;
        for (int i = 0; i < k; i++) { unsigned r = rng() % (unsigned)es.size(); s += es[r]; }
        unsigned rt = rng() % 4u;                   // 随机尾巴：让答案不一定是整串
        for (int i = 0; i < (int)rt; i++) s.push_back(pick());
    }

    if (mode >= 2) {                                // ⚠ 把 S 拆成 2~4 行
        unsigned rl = rng() % 3u;
        int lines = 2 + (int)rl;
        size_t per = (s.size() + (size_t)lines - 1) / (size_t)lines;
        if (per == 0) per = 1;
        for (size_t p = 0; p < s.size(); p += per) printf("%s\n", s.substr(p, per).c_str());
    } else {
        printf("%s\n", s.c_str());
    }
    return 0;
}