[ICPC2019上海B] Prefix Code

[ICPC2019上海B] Prefix Code - Trie

Description

给定 n 个串，问是否存在两个串满足其中一个串是另一个串的前缀。不存在输出 Yes，存在输出 No。（字符串最大长度为 10 ，只包含字符 ‘0’ 到 ‘9’）

Solution

把所有前缀都插入字典树，然后枚举每个原串判断即可

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

#define int long long

struct Trie
{
    struct Node
    {
        int ch[10];
        int val;
    };

    vector<Node> nodes;
    int ind = 0;

    Trie(int siz)
    {
        nodes.resize(siz);
    }

    void insert(const string &str)
    {
        int p = 0;
        for (int i = 0; i < str.length(); i++)
        {
            char c = str[i] - '0';
            nodes[p].val++;
            if (nodes[p].ch[c] == 0)
                nodes[p].ch[c] = ++ind;
            p = nodes[p].ch[c];
        }
        nodes[p].val++;
    }

    int query(const string &str)
    {
        // 检查 str 是否作为一个前缀（不是自己）出现过
        int p = 0;
        for (int i = 0; i < str.length(); i++)
        {
            char c = str[i] - '0';
            p = nodes[p].ch[c];
        }
        return nodes[p].val > 1;
    }
};

void solve()
{
    int n;
    cin >> n;
    Trie trie(n * 12);
    vector<string> strs(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> strs[i];
    for (int i = 1; i <= n; i++)
        trie.insert(strs[i]);
    for (int i = 1; i <= n; i++)
        if (trie.query(strs[i]))
        {
            cout << "No" << endl;
            return;
        }
    cout << "Yes" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}