字典树习题总结

LDUyanhy / 2023-08-12 / 原文

#10049. 「一本通 2.3 例 1」Phone List - 题目 - LibreOJ (loj.ac)

思路：假设 $ T $ 是 $ S $ 的前缀，那么 $ T $ 的长度小于等于 $ S $ 的长度，因此，我们按照字符串的长度对字符串排序后，对其进行插入和查询操作。注意：多组数据，字典树要清空。

#include <bits/stdc++.h>

#define i64 long long

inline int read() {
    bool sym = false; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

const int N = 1e5 + 10;

int trie[N][10], idx;
bool tag[N];

void insert(std::string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int digit = s[i] - '0';
        if (!trie[p][digit]) {
            trie[p][digit] = ++idx;
        }
        p = trie[p][digit];
        tag[p] = true;
    }
}

bool query(std::string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int digit = s[i] - '0';
        if (!trie[p][digit]) {
            return false;
        }
        p = trie[p][digit];
    }
    return tag[p];
} 

int main() {
    int T = read();
    while (T--) {
        int n = read();
        std::memset(trie, 0, sizeof(trie));
        std::memset(tag, false, sizeof(tag));
        idx = 0;
        std::vector<std::string> s(n + 1);
        for (int i = 1; i <= n; i++) std::cin >> s[i];
        std::sort(s.begin() + 1, s.end(), [&](std::string t1, std::string t2) {
            int len1 = t1.size(), len2 = t2.size();
            return len1 > len2;
        });
        insert(s[1]);
        bool check = true;
        for (int i = 2; i <= n; i++) {
            if (query(s[i]) == true) {
                check = false;
            }
            insert(s[i]);
        }
        if (check == true) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}