洛谷 P3879 [TJOI2010] 阅读理解

// P3879 [TJOI2010] 阅读理解 —— 正解：Trie，而**节点上挂的不再是一个数，是一串编号**
//
// ★ 这一章题单走到这里，Trie 的骨架一个字都没变过，变的一直是挂在节点上的东西：
//     [P8306] 一个计数  →  [P2580] 一个三态  →  [P10471] 什么都不挂  →  这道题：**一串文章号**。
//
// ⚠⚠ 而这道题上，**「每个节点开 26 个儿子」这个写法本身过不去**：
//   不同单词的总长顶格 4 760 000 ⇒ `ch[节点][26] × 4 字节` = 472.3 MiB，
//   再加上挂在节点上的东西就撞穿了 512 MiB（p3879Array.cpp 实测峰值 533.2 MiB，**MLE**）。
//   ⇒ 于是这道题成了[本章第 7 步](/ch/50-trie/)那三条出路**第一次真的用得上**的地方：
//     **儿子-兄弟表示法** —— 每个节点只存「左儿子 + 右兄弟 + 这条边上的字符」，
//     26 个指针变成 2 个，代价是「找一个字符」要沿着兄弟链扫（最多 26 步）。
//
// ⚠ 另外两处会咬人的，都不在 Trie 上：
//   ① **去重**：同一个单词在同一篇里可能出现好多次，题面写着「序号不应有重复」。
//      每个单词记住「上一次在哪篇见到」就够了 —— ★ 而这样得到的序号**天然是升序的**
//      （文章按 1..N 顺序读进来），不用排序、不用 set。
//   ② **输出格式**：序号之间一个空格、**第一个前面没有空格**，
//      而「一直没出现过」要输出**一个空行**（不是不输出）。

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

/* 节点数上限 = 不同单词的总长。题面：每篇 ≤ 5000 字符、单词 ≤ 20 字符、N ≤ 1000
   ⇒ 每篇最多 238 个长度 20 的单词 ⇒ 238 × 20 × 1000 = 4 760 000 */
const int MAXN = 4760005;

int son[MAXN];              // 左儿子
int bro[MAXN];              // 右兄弟
char edge_[MAXN];           // 从父亲走到我这条边上的字符
int wordId[MAXN];           // 这个节点是不是某个单词的结尾（0 = 不是；否则是单词编号）
int tot;

vector<vector<int> > where_;   // where_[单词编号] = 它出现在哪几篇
vector<int> lastSeen;          // 这个单词上一次是在第几篇见到的

/** 从 u 往下找字符 c；create = true 时找不到就新开一个 */
int walk(int u, char c, bool create) {
    for (int v = son[u]; v; v = bro[v])
        if (edge_[v] == c) return v;
    if (!create) return 0;
    int v = ++tot;
    edge_[v] = c;
    bro[v] = son[u];        // ★ 新儿子挂到兄弟链的最前面，O(1)
    son[u] = v;
    return v;
}

void addWord(const string& s, int id) {
    int u = 0;
    for (char c : s) u = walk(u, c, true);
    if (!wordId[u]) {                        // 第一次见到这个单词
        wordId[u] = (int)where_.size() + 1;
        where_.push_back(vector<int>());
        lastSeen.push_back(0);
    }
    int w = wordId[u] - 1;
    if (lastSeen[w] == id) return;           // ⚠ ① 这一篇里已经记过了
    lastSeen[w] = id;
    where_[w].push_back(id);
}

int findWord(const string& s) {
    int u = 0;
    for (char c : s) { u = walk(u, c, false); if (!u) return 0; }
    return wordId[u];
}

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

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) {
        int L;
        cin >> L;
        for (int j = 0; j < L; j++) { string w; cin >> w; addWord(w, i); }
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string w;
        cin >> w;
        int id = findWord(w);
        if (id) {
            const vector<int>& v = where_[id - 1];
            for (size_t k = 0; k < v.size(); k++) {
                if (k) cout << ' ';          // ⚠ ② 第一个前面没有空格
                cout << v[k];
            }
        }
        cout << '\n';                        // ⚠ ② 没出现过也要打这一行（空行）
    }
    return 0;
}

// P3879 的两笔账：Trie 到底有多少个节点，以及三种存法各要多少内存
//
// 用法：./p3879Count <csv|table> < 一份输入
//
// ★ 节点数 = 所有**不同单词**的不同前缀个数 —— 把不同的单词排好序，
//   数「每个单词比上一个多出来的那几位」就行，不用真去建那棵树。
//   ⇒ 而这道题的关键就是这个数：它一乘 26 再乘 4，就是 26 叉静态数组要占的字节。

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

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

    int n;
    if (!(scanf("%d", &n) == 1)) return 0;
    static char buf[64];
    set<string> uniq;
    long long totalWords = 0, totalChars = 0;
    long long pairs = 0;                       // (单词, 篇号) 的不同组合数 = 所有答案加起来有多长
    set<pair<string, int> > pr;
    for (int i = 1; i <= n; i++) {
        int L;
        if (scanf("%d", &L) != 1) break;
        for (int j = 0; j < L; j++) {
            if (scanf("%60s", buf) != 1) break;
            string w = buf;
            totalWords++;
            totalChars += (long long)w.size();
            uniq.insert(w);
            pr.insert(make_pair(w, i));
        }
    }
    pairs = (long long)pr.size();

    long long nodes = 0, uniqChars = 0;
    {
        string prev;
        for (set<string>::iterator it = uniq.begin(); it != uniq.end(); ++it) {
            const string& s = *it;
            uniqChars += (long long)s.size();
            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;
        }
    }

    vector<pair<string, long long> > out;
    out.push_back(make_pair("articles", n));
    out.push_back(make_pair("words", totalWords));
    out.push_back(make_pair("chars", totalChars));
    out.push_back(make_pair("uniq_words", (long long)uniq.size()));
    out.push_back(make_pair("uniq_chars", uniqChars));
    out.push_back(make_pair("nodes", nodes));
    out.push_back(make_pair("pairs", pairs));
    /* 三种存法的字节数（×100 之后取整，好写成断言） */
    out.push_back(make_pair("mib26_x100", (long long)(nodes * 26.0 * 4 * 100 / 1048576.0)));
    out.push_back(make_pair("mibsib_x100", (long long)(nodes * 13.0 * 100 / 1048576.0)));

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%lld\n", out[i].first.c_str(), out[i].second);
    else for (size_t i = 0; i < out.size(); i++) printf("  %-14s %lld\n", out[i].first.c_str(), out[i].second);
    return 0;
}