洛谷 P8306 【模板】字典树

// P8306【模板】字典树 —— 正解：Trie，O(总长)
//
// ★ 骨架和本章第 5 步那份 fast.cpp 一模一样，可这道**真题**上有三处要重新算一遍：
//
//   ① ⚠⚠ **字符集是 62 不是 26** —— 题面写着「只含大小写字母和数字」，
//      而且专门补了一句「大小写敏感，Fusu 和 fusu 不同」。
//      ⇒ 拿 `c - 'a'` 配 26 列，'0' 会算出 -49（负下标写数组 = UB），'A' 算出 -32。
//   ② ⚠⚠ **内存要按 62 列重算**：3×10⁶ × 62 × 4 字节 = **709.5 MiB**。
//      而这道题的内存限制是 **1048576 KB = 1024 MiB** —— 那不是慷慨，是刚好够。
//      （本章正文那张表算的是 26 列 × 10⁶ = 104 MB，这里是它的 7.15 倍。）
//   ③ ⚠ **多测**：T 可以到 10⁵，而 memset 整个 ch 是 709.5 MiB 的活 ——
//      T 遍就是 71 TB。⇒ 只清用过的那 tot + 1 个节点（clearUsed）。
//
// ★ 而这道题只问一个数：「有多少个 sⱼ 以 t 为前缀」= cntPass。
//   cntEnd 在这道题上一次都用不到 —— 本章那两个计数，这里只用了一个。

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

/* 节点数上限 = 所有字符串的总长 + 1（每个字符最多新开一个节点，再加一个根） */
const int MAXN = 3000005;
const int SIGMA = 62;

int ch[MAXN][SIGMA];     // ⚠ 709.5 MiB —— 这道题给了 1024 MiB，刚好够
int cntPass[MAXN];       // 有多少个字符串路过这个节点
int tot;                 // 已经用掉的最大节点编号（0 号是根）

/** ★ 62 个字符 → 0..61：数字 0~9、大写 10~35、小写 36~61 */
inline int idx(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    return c - 'a' + 36;
}

void insertWord(const string& s) {
    int u = 0;
    for (char c : s) {
        int k = idx(c);
        if (!ch[u][k]) ch[u][k] = ++tot;
        u = ch[u][k];
        cntPass[u]++;
    }
}

/** 以 s 为前缀的字符串有几个 */
int ask(const string& s) {
    int u = 0;
    for (char c : s) {
        int k = idx(c);
        if (!ch[u][k]) return 0;                // ⚠ 走不下去 ⇒ 一个都没有，立刻返回
        u = ch[u][k];
    }
    return cntPass[u];
}

/** ★ 只清用过的那 tot + 1 个节点 —— 不是 memset 整个数组 */
void clearUsed() {
    for (int i = 0; i <= tot; i++) {
        memset(ch[i], 0, sizeof(ch[i]));
        cntPass[i] = 0;
    }
    tot = 0;
}

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; i++) { string s; cin >> s; insertWord(s); }
        for (int i = 0; i < q; i++) { string p; cin >> p; cout << ask(p) << '\n'; }
        clearUsed();
    }
    return 0;
}

// P8306 的三笔账：内存、清空、次数 —— 全部用**机器无关**的量来数
//
// 用法：./p8306Count csv        （给 check-viz.mjs 读的 key,value）
//       ./p8306Count table      （给人看的表）
//
// ★ 为什么这一份不真去建那棵 62 叉树：**用不着**。
//   Trie 的节点数 = 所有字符串的**不同前缀个数**，而把字符串排好序之后
//   它就等于 `Σ (len_i − lcp(s_i, s_{i−1}))` —— 一句话就数完了，
//   不用为了数一个数去申请 709.5 MiB。
//   ⇒ 而这也正好是本章第 7 步那句话的另一种说法：**空间是「不同前缀的个数」**。

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

static mt19937 rng(20260910u);
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

static const char* AL62 =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

/** 节点数 = Σ (len_i − lcp(排序后相邻两个)) */
static long long trieNodes(vector<string> v) {
    sort(v.begin(), v.end());
    long long nodes = 0;
    string prev;
    for (const string& s : v) {
        size_t l = 0;
        while (l < s.size() && l < prev.size() && s[l] == prev[l]) l++;
        nodes += (long long)s.size() - (long long)l;
        prev = s;
    }
    return nodes;
}

/** 造总长为 total 的一批串：shape = long / short / low3 / share */
static vector<string> makeShape(const string& shape, long long total) {
    vector<string> v;
    long long used = 0;
    while (used < total) {
        string s;
        if (shape == "long") {                      // 长串、62 个字符随便抽
            int len = (int)min<long long>(15, total - used);
            for (int i = 0; i < len; i++) s += AL62[ri(0, 61)];
        } else if (shape == "short") {              // 短串、62 个字符
            int len = (int)min<long long>(4, total - used);
            for (int i = 0; i < len; i++) s += AL62[ri(0, 61)];
        } else if (shape == "low3") {               // 只有 3 个字母
            int len = (int)min<long long>(15, total - used);
            for (int i = 0; i < len; i++) s += (char)('a' + ri(0, 2));
        } else {                                    // share：都以同一段开头
            int len = (int)min<long long>(15, total - used);
            s = string("prefixprefix").substr(0, min<size_t>(12, (size_t)len));
            while ((int)s.size() < len) s += AL62[ri(0, 61)];
        }
        used += (long long)s.size();
        v.push_back(s);
    }
    return v;
}

/** ★ 从 stdin 读一份**真的输入**，报「名单一共多少字符 / Trie 多少节点 / 62 列要多少 MiB」 */
static int fromInput() {
    int T;
    if (!(scanf("%d", &T) == 1)) return 0;
    long long chars = 0, nodes = 0, words = 0, maxNodes = 0;
    static char buf[100005];
    for (int t = 0; t < T; t++) {
        int n, q;
        if (scanf("%d %d", &n, &q) != 2) break;
        vector<string> v;
        for (int i = 0; i < n; i++) { if (scanf("%100004s", buf) != 1) break; v.push_back(buf); }
        for (int i = 0; i < q; i++) { if (scanf("%100004s", buf) != 1) break; }
        for (const string& s : v) chars += (long long)s.size();
        words += (long long)v.size();
        long long here = trieNodes(v);
        nodes += here;
        maxNodes = max(maxNodes, here);        // ⚠ 多组之间树是清空的 ⇒ **峰值**是各组的最大值，不是总和
    }
    printf("words,%lld\nchars,%lld\nnodes,%lld\nmaxnodes,%lld\nmib,%.1f\n",
           words, chars, nodes, maxNodes, (double)maxNodes * 62 * 4 / 1048576.0);
    return 0;
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (mode == "input") return fromInput();
    const long long TOTAL = 3000000;               // 题面顶格：输入字符串总长 3×10⁶
    const long long MAXN = 3000005, SIGMA = 62;

    vector<pair<string, string>> out;
    auto put = [&](const string& k, const string& v) { out.push_back({k, v}); };
    auto num = [](long long x) { return to_string(x); };

    /* ① 内存账：四种形状，节点数差多少 */
    for (const string& sh : {string("long"), string("short"), string("low3"), string("share")}) {
        vector<string> v = makeShape(sh, TOTAL);
        long long nodes = trieNodes(v);
        put(sh + "_words", num((long long)v.size()));
        put(sh + "_nodes", num(nodes));
        char buf[64];
        snprintf(buf, sizeof(buf), "%.1f", (double)nodes * SIGMA * 4 / 1048576.0);
        put(sh + "_mib", buf);
    }
    {
        char buf[64];
        snprintf(buf, sizeof(buf), "%.1f", (double)MAXN * SIGMA * 4 / 1048576.0);
        put("array_mib", buf);                     // 静态数组本身开多大
        put("limit_mib", num(1048576 / 1024));     // 题面给的 1048576 KB
        snprintf(buf, sizeof(buf), "%.1f", (double)1000000 * 26 * 4 / 1048576.0);
        put("chapter_mib", buf);                   // 本章正文那张表：26 列 × 10⁶
        snprintf(buf, sizeof(buf), "%.2f",
                 ((double)MAXN * SIGMA) / (1000000.0 * 26));
        put("vs_chapter", buf);                    // 这道真题是正文那笔账的几倍
    }

    /* ② 清空账：顶格 T = 10⁵ 组，每组平均只有 30 个字符 */
    {
        long long T = 100000;
        long long perGroup = TOTAL / T;            // 每组 30 个字符 ⇒ 至多 30 个节点
        long long goodCells = T * (perGroup + 1) * (SIGMA + 1);   // 只清用过的：(tot+1) × (62 列 + 1 个计数)
        long long badCells  = T * MAXN * (SIGMA + 1);             // memset 整个数组
        put("clear_T", num(T));
        put("clear_good", num(goodCells));
        put("clear_bad", num(badCells));
        put("clear_ratio", num(badCells / goodCells));
        char buf[64];
        snprintf(buf, sizeof(buf), "%.1f", (double)T * MAXN * SIGMA * 4 / 1e12);
        put("clear_tb", buf);                      // memset 一共抹写多少 TB
    }

    /* ③ 次数账：顶格一组 n = q = 10⁵、串长 15 —— 暴力比几个字符，Trie 走几步 */
    {
        long long n = 100000, q = 100000, len = 15;
        put("brute_steps", num(n * q));            // 每次询问至少要看 n 个串一眼
        put("trie_steps", num((n + q) * len));     // 每个字符走一步，插入 + 查询各一遍
        put("steps_ratio", num((n * q) / ((n + q) * len)));
    }

    /* ④ 输出账：题面一个字都没提，可它是真的大 */
    {
        /* 让答案尽量多位：n = 10⁵ 个 "a"，q = 10⁵ 次问 "a" ⇒ 每行 "100000\n" = 7 字节。
           一组用掉 2×10⁵ 个字符，总长 3×10⁶ ⇒ 最多 15 组。 */
        long long groups = TOTAL / (100000 + 100000);
        long long lines = groups * 100000;
        put("out_groups", num(groups));
        put("out_lines", num(lines));
        put("out_bytes", num(lines * 7));
        char buf[64];
        snprintf(buf, sizeof(buf), "%.1f", (double)lines * 7 / 1048576.0);
        put("out_mib", buf);
    }

    if (mode == "csv") {
        for (auto& kv : out) printf("%s,%s\n", kv.first.c_str(), kv.second.c_str());
    } else {
        for (auto& kv : out) printf("  %-16s %s\n", kv.first.c_str(), kv.second.c_str());
    }
    return 0;
}

// P8306 的 I/O 账：题面说「本题不卡常」—— 那句话有没有主语？
//
// 用法：./p8306Io read  <sync|nosync|scanf|fread> <输入文件>
//       ./p8306Io write <endl|nl|endlfast|nosync|printf|buf> <输入文件> [答案文件] [计时文件]
//   （write 的六种：默认同步 + endl ／ 默认同步 + '\n' ／ **关同步 + endl** ／
//     关同步 + '\n' ／ printf ／ 自写缓冲）
//   ★★ 那个「关同步 + endl」不是凑数的 —— [第 48 章 P3375](/sol/p3375/) 量到
//     「endl → '\n' 值 8.8 倍」，而这道题上只值 1.1 倍。差别就藏在**有没有关同步**里。
//   ⚠ 外加两个**对照**：none / nonefast —— 一模一样地做完这道题，只是**一个字都不打**。
//     ★ 没有它们，这张表量的是「读 + 算 + 写」，而这道题的读入有 3×10⁶ 个 token，
//       默认 cin 在那一侧的开销比整个输出还大，会把 endl 那一项整个淹掉
//       （[第 47 章 P1308](/sol/p1308/) 那条：**量什么都要先问一句「这个数里有没有别人的份」**）。
//   两条都打一行 `mode,毫秒,读到的串数,读到的字节数,写出的字节数`：
//   给了「计时文件」就写进那个文件，否则写 stderr。
//   ⚠ 答案本身走 stdout（默认就是屏幕）—— 给了「答案文件」就 freopen 到那儿去，
//     这样 stdout 上那 10 MiB 才不会跟着计时一起被读走。
//
// ⚠ 一律用 freopen 从**文件**读 —— 评测机就是这么干的。
//   （第 47 章 [P1308] 那一跤：从 node 的管道读会多出一截**加性**开销，
//     四种读法各自多出来的都不到 1 毫秒，可占比从 8% 到 50% 上下，
//     **只有最快的那一版看得见它**。）

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

static double nowMs() {
    struct timeval tv; gettimeofday(&tv, nullptr);
    return tv.tv_sec * 1000.0 + tv.tv_usec / 1000.0;
}

const int MAXN = 3000005, SIGMA = 62;
static int ch[MAXN][SIGMA];
static int cntPass[MAXN];
static int tot;

inline int idx(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    return c - 'a' + 36;
}

/* ---- 自写缓冲：读 ---- */
static char inbuf[1 << 22];
static size_t inLen = 0, inPos = 0;
static inline int gc() {
    if (inPos == inLen) { inLen = fread(inbuf, 1, sizeof(inbuf), stdin); inPos = 0; if (!inLen) return -1; }
    return inbuf[inPos++];
}
static bool readTokenFast(string& s) {
    int c = gc();
    while (c == ' ' || c == '\n' || c == '\r') c = gc();
    if (c < 0) return false;
    s.clear();
    while (c > ' ') { s += (char)c; c = gc(); }
    return true;
}

/* ---- 自写缓冲：写 ---- */
static char obuf[1 << 22];
static size_t oPos = 0;
static inline void flushOut() { fwrite(obuf, 1, oPos, stdout); oPos = 0; }
static inline void writeIntFast(int x) {
    if (oPos + 16 > 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 what = argc > 1 ? argv[1] : "read";
    string mode = argc > 2 ? argv[2] : "nosync";
    if (argc > 3 && !freopen(argv[3], "r", stdin)) return 1;
    if (argc > 4 && !freopen(argv[4], "w", stdout)) return 1;
    const char* statPath = argc > 5 ? argv[5] : nullptr;

    long long strs = 0, bytes = 0, outBytes = 0;
    auto report = [&](const char* m, double ms) {
        FILE* f = statPath ? fopen(statPath, "w") : stderr;
        if (!f) return;
        fprintf(f, "%s,%.1f,%lld,%lld,%lld\n", m, ms, strs, bytes, outBytes);
        if (statPath) fclose(f);
    };
    double t0 = nowMs();

    if (what == "read") {
        /* 只读，什么都不算 —— 量的是纯读入 */
        if (mode == "sync" || mode == "nosync") {
            if (mode == "nosync") { ios::sync_with_stdio(false); cin.tie(nullptr); }
            string s;
            while (cin >> s) { strs++; bytes += (long long)s.size(); }
        } else if (mode == "scanf") {
            static char buf[10005];
            while (scanf("%10004s", buf) == 1) { strs++; bytes += (long long)strlen(buf); }
        } else {
            string s;
            while (readTokenFast(s)) { strs++; bytes += (long long)s.size(); }
        }
        report(mode.c_str(), nowMs() - t0);
        return 0;
    }

    /* what == write：真做一遍这道题，只换「怎么把答案打出去」 */
    if (mode != "endl" && mode != "nl" && mode != "none") { ios::sync_with_stdio(false); cin.tie(nullptr); }

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, q; cin >> n >> q;
        for (int i = 0; i < n; i++) {
            string s; cin >> s; strs++; bytes += (long long)s.size();
            int u = 0;
            for (char c : s) { int k = idx(c); if (!ch[u][k]) ch[u][k] = ++tot; u = ch[u][k]; cntPass[u]++; }
        }
        for (int i = 0; i < q; i++) {
            string p; cin >> p; strs++; bytes += (long long)p.size();
            int u = 0, ans = 0;
            bool ok = true;
            for (char c : p) { int k = idx(c); if (!ch[u][k]) { ok = false; break; } u = ch[u][k]; }
            if (ok) ans = cntPass[u];
            { int x = ans; int d = 1; while (x >= 10) { x /= 10; d++; } outBytes += d + 1; }
            if (mode == "none" || mode == "nonefast") { /* 对照：什么都不打 */ }
            else if (mode == "endl" || mode == "endlfast") cout << ans << endl;
            else if (mode == "printf") printf("%d\n", ans);
            else if (mode == "buf") writeIntFast(ans);
            else cout << ans << '\n';
        }
        for (int i = 0; i <= tot; i++) { memset(ch[i], 0, sizeof(ch[i])); cntPass[i] = 0; }
        tot = 0;
    }
    if (mode == "buf") flushOut();
    cout.flush();
    fflush(stdout);
    report(mode.c_str(), nowMs() - t0);
    return 0;
}