XCPC wiki - 字符串 03 - 字典树

char	ascii
0	48
9	57
A	65
Z	90
a	97
z	122

经典字典树

主机场

给定一组字符串$s_1,s_2,\cdots,s_n$，任选$k$ 个$s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})$，最小化$\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})$。其中$\operatorname{lcp}(p,q)$ 是字符串$p$ 和字符串$q$ 的最长公共前缀，字符串的大小即为其字典序的大小。数据范围：$2\leqslant k\leqslant n\leqslant 10^6$ 且$\sum |s_i|\le 10^6$。（2023GDCPC E. New but Nostalgic Problem）

#include <iostream>
#include <cstring>
#include <algorithm>
constexpr int N = 5e6 + 8;
using ll = long long;
using namespace std;

struct Trie {
    static constexpr char base = 'a';
    static constexpr int tot = 26;
    int pcnt;        // 总节点数
    int vis[N];      // 是否访问过
    int dep[N];      // 字典树深度
    int ecnt[N];     // 以该节点为末字符的字符串数量
    int icnt[N];     // 经过该节点的字符串数量
    int nxt[N][tot]; // 存的是子树编号

    void init(int p) {
        vis[p] = icnt[p] = ecnt[p] = 0;
        memset(nxt[p], 0, sizeof nxt[p]);
    }  // 用什么init什么

    void init() {
        pcnt = 1;
        init(1);
    }

    void insert(const string& s, int p = 1) {
        ++icnt[p];
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) nxt[p][c] = ++pcnt, init(pcnt);
            p = nxt[p][c];
            ++icnt[p];  // 经过该节点的字符串数量
            dep[p] = i + 1;
        }
        ++ecnt[p];   // 以该节点为末字符的字符串数量
    }

    int find(const string& s, int p = 1) {
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) return 0;
            p = nxt[p][c];
        }
        return p;
    }

    void solve(int k, int p = 1) {
        // 逐位确定答案，p 表示目前已确定的答案前缀在 trie 上是哪个节点
        int num = 0;   // 已经选择的数量
        while (1) {
            // 判断答案是否就是 p 所在的节点
            num += ecnt[p];  // 以p为末字符的字符串一定都可以选
            for (int i = 0; i < tot; ++i) {
                if (icnt[nxt[p][i]]) num++;  // 该节点的下一位base+i有字符串经过
            }
            if (num >= k) {
                cout << (p == 1 ? "EMPTY\n" : "\n");
                return;
            }
            for (int i = 0; i < tot; ++i) {
                if (icnt[nxt[p][i]]) {  // 该节点的下一位base+i有字符串经过
                    // 比i小的子树里的字符串都可以选
                    num += icnt[nxt[p][i]] - 1;  // 这里-1的原因是上一个循环已经加过1了
                    if (num >= k) {
                        num -= icnt[nxt[p][i]];  // 当前子数不确定 减掉 留到下一个字符
                        p = nxt[p][i];
                        cout << char(i + base);
                        break;
                    }
                }
            }
        }
    }
} T;

void eachT() {
    int n, k;
    cin >> n >> k;

    T.init();

    while (n--) {
        string s;
        cin >> s;
        T.insert(s);
    }

    T.solve(k);
}

int main() {
    int T;
    cin >> T;
    while (T--) eachT();

    return 0;
}

宠物对战

将 A 类字符串和 B 类字符串交替拼接为给定字符串$T$，最小化字符串数量。数据范围：$1\leqslant n,m\leqslant 10^5$，$\sum |s_i|\leqslant 5\times10^5$ 且$|T| \leqslant 5000$。（2022女生赛 I. 宠物对战）

设$f[i,op]$ 表示拼接$T$ 的前$i$ 位，且以$op$ 串结尾的所需最小化字符串数量。

#include <iostream>
#include <cstring>
#include <algorithm>
constexpr int N = 5e5 + 8;
using ll = long long;
using namespace std;

struct Trie {
    static constexpr char base = 'a';
    static constexpr int tot = 26;
    int pcnt;        // 总节点数
    int vis[N];      // 是否访问过
    int dep[N];      // 字典树深度
    int ecnt[N];     // 以该节点为末字符的字符串数量
    int icnt[N];     // 经过该节点的字符串数量
    int nxt[N][tot];  // 存的是子树编号

    void init(int p) {
        vis[p] = icnt[p] = ecnt[p] = 0;
        memset(nxt[p], 0, sizeof nxt[p]);
    }  // 用什么init什么

    void init() {
        pcnt = 1;
        init(1);
    }

    void insert(const string& s, int p = 1) {
        ++icnt[p];
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) nxt[p][c] = ++pcnt, init(pcnt);
            p = nxt[p][c];
            ++icnt[p];  // 经过该节点的字符串数量
            dep[p] = i + 1;
        }
        ++ecnt[p];   // 以该节点为末字符的字符串数量
    }

    int find(const string& s, int p = 1) {
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) return 0;
            p = nxt[p][c];
        }
        return p;
    }
} T[2];

int f[5008][2];  // 前i个字符最少数量
void eachT() {
    int n;
    string s;

    T[0].init();
    cin >> n;
    while (n--) {
        cin >> s;
        T[0].insert(s);  // 插入A
    }

    T[1].init();
    cin >> n;
    while (n--) {
        cin >> s;
        T[1].insert(s);  // 插入B
    }

    cin >> s;
    n = s.length();
    s = ' ' + s;

    memset(f, 0x3f, sizeof f);
    f[0][1] = f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int op = 0; op <= 1; ++op) {
            int p = 1;
            for (int j = i; j <= n; ++j) {
                auto c = s[j] - base;
                if (!T[op].nxt[p][c]) break;
                p = T[op].nxt[p][c];
                if (T[op].ecnt[p]) {
                    f[j][op] = min(f[j][op], f[i - 1][op ^ 1] + 1);
                }
            }
        }
    }

    int ans = min(f[n][0], f[n][1]);
    if (ans == 0x3f3f3f3f) ans = -1;
    printf("%d\n", ans);
}

int main() {
    eachT();
    return 0;
}

模板

公共前缀

给出$n$ 个字符串。$q$ 次询问，每次给出一个字符串$T$，输出在所有给出的字符串中与$T$ 的某个前缀相同的个数。数据范围：$1\leqslant n,q\leqslant 5\times10^5$，$\sum |s_i|\leqslant 5\times10^6$。

#include <iostream>
#include <cstring>
#include <algorithm>
constexpr int N = 5e6 + 8;
using ll = long long;
using namespace std;

struct Trie {
    static constexpr char base = 'a';
    static constexpr int tot = 26;
    int pcnt;        // 总节点数
    int vis[N];      // 是否访问过
    int dep[N];      // 字典树深度
    int ecnt[N];     // 以该节点为末字符的字符串数量
    int icnt[N];     // 经过该节点的字符串数量
    int nxt[N][tot];  // 存的是子树编号

    void init(int p) {
        vis[p] = icnt[p] = ecnt[p] = 0;
        memset(nxt[p], 0, sizeof nxt[p]);
    }  // 用什么init什么

    void init() {
        pcnt = 1;
        init(1);
    }

    void insert(const string& s, int p = 1) {
        ++icnt[p];
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) nxt[p][c] = ++pcnt, init(pcnt);
            p = nxt[p][c];
            ++icnt[p];  // 经过该节点的字符串数量
            dep[p] = i + 1;
        }
        ++ecnt[p];   // 以该节点为末字符的字符串数量
    }

    int find(const string& s, int p = 1) {
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) return 0;
            p = nxt[p][c];
        }
        return p;
    }

    // 公共前缀
    int findcp(const string& s) {
        int p = 1;
        ll sum = 0;
        for (auto& c : s) {
            sum += ecnt[p];
            if (!nxt[p][c - 48]) return sum;
            p = nxt[p][c - 48];
        }
        return sum += icnt[p];
    }
} T;

void eachT() {
    int n, q;
    cin >> n >> q;

    T.init();

    while (n--) {
        string s;
        int m;
        cin >> m;
        while (m--) {
            int x;
            cin >> x;
            s += (char)(x + '0');
        }
        T.insert(s); // 插入
    }

    while (q--) {
        string s;
        int m;
        cin >> m;
        while (m--) {
            int x;
            cin >> x;
            s += (char)(x + '0');
        }
        printf("%d\n", T.findcp(s));
    }
}

int main() {
    eachT();
    return 0;
}

遍历字典树

外星联络

求 01 串中所有重复出现次数大于$1$ 的子串的数量，按字典序排序。

constexpr int N = 1e7 + 8;
struct Trie {
    static constexpr char base = '0';
    static constexpr int tot = 2;

    // ...

    void solve() {
        auto dfs = [&](auto&& self, int p) -> void {
            if (icnt[p] > 1 && p > 1) {
                cout << icnt[p] << endl;
            }
            for (int i = 0; i < tot; ++i) {
                if (!nxt[p][i]) continue;
                self(self, nxt[p][i]);
            }
        };
        dfs(dfs, 1);
    }
} T;

void eachT() {
    int n;
    string s;
    cin >> n >> s;

    T.init();

    for (int i = 0; i < n; ++i) {
        T.insert(s.substr(i));
    }

    T.solve();
}

2022 ICPC 杭州 K. Master of Both

给出$n$ 个字符串，以及$q$ 次询问，每次询问给出一个字母之间的大小顺序，问在该顺序下这$n$ 个字符串的逆序对个数。([[…/contests/VP/2024-09-25-Autumn2-2022ICPC杭州|2024-09-25-Autumn2-2022ICPC杭州]])

constexpr int N = 2e6 + 8, tot = 27;
constexpr char base = 'a' - 1;

int nxt[N][tot];
int pcnt;
int cnt[N][tot];
ll dp[tot][tot];

void insert(const string& s, int p = 1) {
    for (auto C : s) {
        int c = C - base;
        if (!nxt[p][c]) nxt[p][c] = ++pcnt;
        for (int i = 0; i < tot; ++i) {
            if (i == c) continue;
            dp[c][i] += cnt[p][i];
        }
        cnt[p][c] += 1;
        p = nxt[p][c];
    }
}

void eachT() {
    int n, q;
    cin >> n >> q;

    pcnt = 1;

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        s = s + base;
        insert(s);
    }

    while (q--) {
        string s;
        cin >> s;
        s = base + s;
        ll ans = 0;
        for (int l = 0; l < tot; ++l) {
            for (int r = l + 1; r < tot; ++r) {
                ans += dp[s[l] - base][s[r] - base];
            }
        }
        cout << ans << '\n';
    }
}

2023 ICPC 网络赛 (I) F. Alice and Bob

给定一个序列，从中选出一个三元组进行游戏。游戏的规则是：每次从中选两个数将它们换成和不变，绝对值之差更小的两个数，无法操作者败。问有多少种选法满足先手必胜。

满足以下条件之一：

1. 三个数互不相同；
2. 两个数互不相同，且这两个值的差的二进制表示下的最小的 1 的位置为奇。

int pcnt = 0;
int vis[N];
int dep[N];
int ecnt[N];
int t[N][2];
ll w1[N], w2[N];

void init(int p) {
    vis[p] = ecnt[p] = 0;
    t[p][0] = t[p][1] = 0;
    w1[p] = w2[p] = 0;
}

void init() {
    pcnt = 1;
    init(1);
}

void insert(const ll x, int p = 1) {
    for (int bit = 0; bit <= D; ++bit) {
        bool c = x & (1ll << bit);
        if (!t[p][c]) t[p][c] = ++pcnt, init(pcnt);
        p = t[p][c];
        dep[p] = bit + 1;
    }
    ++ecnt[p];
}

ll C3(ll n) {
    if (n < 3) return 0;
    return n * (n - 1) / 2 * (n - 2) / 3;
}

ll C2(ll n) {
    if (n < 2) return 0;
    return n * (n - 1) / 2;
}

ll res;
void dfs(int p = 1) {
    if (ecnt[p]) {
        w1[p] = ecnt[p];
        w2[p] = C2(ecnt[p]);
        res -= C3(ecnt[p]);
    }
    if (t[p][0]) {
        dfs(t[p][0]);
        w1[p] += w1[t[p][0]];
        w2[p] += w2[t[p][0]];
    }
    if (t[p][1]) {
        dfs(t[p][1]);
        w1[p] += w1[t[p][1]];
        w2[p] += w2[t[p][1]];
    }
    if (dep[p] % 2 == 0 && t[p][0] && t[p][1]) {
        res -= w1[t[p][0]] * w2[t[p][1]];
        res -= w1[t[p][1]] * w2[t[p][0]];
    }
}

void eachT() {
    int n = read();

    init();
    for (int i = 1; i <= n; ++i) {
        ll x = read();
        insert(x);
    }

    res = C3(n);
    dfs();
    cout << res << '\n';
}

字典树上 DP

Rima 洛谷-P7537

题意 若$\operatorname{lcs}(s_{1},s_{2}) \geqslant \max(|s_{1}|,|s_{2}|)-1$，称$s_{1},s_{2}$ 两个字符串 押韵。用$n$ 个给定的互不相同的字符串组合出一个的字符串序列$T$，使得序列中相邻两个字符串 押韵。最大化$T$ 的元素数量。数据范围：$n \leqslant 5\times10^{5}$，$\sum|s| \leqslant 3 \times 10^6$。

思路 事实上，两字符串押韵只有三种情形：

• 形如$a-S,b-S$；
• 形如$a-S,S$；
• 形如$S,S$（不可能，题给字符串互不相同）。

将字符串反转并建立 字典树。由于字典树上每个$\operatorname{ecnt}$ 存在的点都代表一个字符串，要将字符串连接成一个序列，即是找到树上的最长链，即找 树的直径，进而转化为找最长链和次长链。

#include <iostream>
#include <algorithm>
constexpr int N = 3e6 + 8;
using namespace std;

constexpr char base = 'a';
constexpr int tot = 26;
int pcnt;        // 总节点数
int ecnt[N];     // 以该节点为末字符的字符串数量
int nxt[N][tot]; // 存的是子树编号

void insert(const string& s, int p = 1) {
    for (auto& c : s) {
        if (!nxt[p][c - base]) nxt[p][c - base] = ++pcnt;
        p = nxt[p][c - base];
    }
    ++ecnt[p];   // 以该节点为末字符的字符串数量
}

int d, dp1[N], dp2[N];  // 直径 最长链 次长链
void dfs(int p) {
    int cnt = 0;  // 子节点数量
    for (int i = 0; i < tot; ++i) {
        int& v = nxt[p][i];
        if (!v) continue;
        dfs(v);

        if (!ecnt[v]) continue;  // 这里没有节点 不可能连出一条链
        cnt += ecnt[v];
        int& t = dp1[v];
        if (t > dp1[p]) dp2[p] = dp1[p], dp1[p] = t;
        else if (dp1[v] > dp2[p]) dp2[p] = t;
    }
    d = max(d, cnt + dp1[p] + ecnt[p] + dp2[p]);
    dp1[p] += cnt;
}

int main() {
    pcnt = 1;   // 初始化

    int m;
    cin >> m;
    while (m--) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        insert(s);  // 插入
    }

    dfs(1);

    cout << d << '\n';

    return 0;
}

病毒检测 洛谷-P2536

题意 给定一个母串$S$，并给定$n$ 个子串$T$，$S$ 包括若干个字符：

• ?：可以替换为任意一个大写字母。
• *：可以替换为任意长度为$l \in [0,\infty)$ 的字符串。
• 其他大写字母：无说明。

将 ? 和 * 替换后形成的大写字母串称为$S$ 的配合串，求$n$ 个子串$T$ 中有多少个不是$S$ 的配合串。

思路 设状态$f(p,q)$ 表示子串的前$p$ 个字符和母串的前$q$ 个字符匹配的方案数。

多个 * 的情形不需要特判，这几行代码可以省略：

stack<char> Q;
for (auto &c : s) if (c != '*' || Q.empty() || Q.top() != '*') Q.push(c);
s = "";
while (!Q.empty()) s = Q.top() + s, Q.pop();

#include <iostream>
#include <algorithm>
constexpr int N = 2e5 + 8;
using namespace std;

string s;

int ch(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'T') return 2;
    if (c == 'G') return 3;
    return -1;
}

constexpr int tot = 4;
int pcnt = 0;
int nxt[N][tot];
int ecnt[N];
void insert(const string& s, int p = 1) {
    for (auto& c : s) {
        if (!nxt[p][ch(c)]) nxt[p][ch(c)] = ++pcnt;
        p = nxt[p][ch(c)];
    }
    ++ecnt[p];
}

int ans = 0;
bool vis[N][508];
void dfs(int p, int si) {
    if (vis[p][si]) return;
    vis[p][si] = 1;

    if (si == s.size()) {
        ans += ecnt[p];
        return;
    }

    if (s[si] == '*') {
        dfs(p, si + 1);
        for (int i = 0; i <= 3; ++i) {
            if (nxt[p][i]) dfs(nxt[p][i], si);
        }
    }
    else if (s[si] == '?') {
        for (int i = 0; i <= 3; ++i) {
            if (nxt[p][i]) dfs(nxt[p][i], si + 1);
        }
    }
    else {
        int i = ch(s[si]);
        if (nxt[p][i]) dfs(nxt[p][i], si + 1);
    }
}

int main() {
    pcnt = 1;

    cin >> s;

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string t;
        cin >> t;
        insert(t);
    }

    dfs(1, 0);

    cout << n - ans << '\n';

    return 0;
}

字符串游戏 51Nod-1490

[[…/数学/博弈论#H. 字符串游戏 51Nod-1490]]

最新版

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

struct Trie {
    static constexpr int N = 2e6 + 8;
    static constexpr char base = 'a';
    static constexpr int tot = 26;
    int pcnt;        // 总节点数
    int vis[N];      // 是否访问过
    int dep[N];      // 字典树深度
    int ecnt[N];     // 以该节点为末字符的字符串数量
    int icnt[N];     // 经过该节点的字符串数量
    int nxt[N][tot]; // 存的是子树编号

    void init(int p) {
        vis[p] = icnt[p] = ecnt[p] = 0;
        memset(nxt[p], 0, sizeof nxt[p]);
    }  // 用什么init什么

    void init() {
        pcnt = 1;
        init(0);   // 根节点是 0
    }

    void insert(const string& s, int p = 0) {
        icnt[p]++;
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i] - base;
            if (!nxt[p][c]) init(nxt[p][c] = pcnt++);
            p = nxt[p][c];
            icnt[p]++;  // 经过该节点的字符串数量
            dep[p] = i;
        }
        ecnt[p]++;
    }
} T;

int main() {
    int n;
    cin >> n;

    T.init();

    ll res = 0;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        T.insert(s[i]);
        res += 1LL * s[i].size() * 2 * n;
    }
    for (int i = 1; i < T.pcnt; ++i) {
        res += 1LL * T.icnt[i] * T.icnt[i];
    }

    T.init();
    for (int i = 0; i < n; i++) {
        T.insert(s[i]);
        reverse(s[i].begin(), s[i].end());
        T.insert(s[i]);
    }
    for (int i = 1; i < T.pcnt; ++i) {
        res -= 1LL * T.icnt[i] * T.icnt[i];
    }

    T.init();
    for (int i = 0; i < n; i++) {
        T.insert(s[i]);
    }
    for (int i = 1; i < T.pcnt; ++i) {  // 这里 [1, pcnt)
        res += 1LL * T.icnt[i] * T.icnt[i];
    }

    cout << res << endl;
    
    return 0;
}