【题目描述】
原题来自：POJ 3630

给定 n 个长度不超过 10 的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀，多组数据。

【输入】
第一行一个整数 T，表示数据组数。

对于每组数据，第一行一个数 n，接下来 n 行输入 n 个数字串。

【输出】
对于每组数据，若存在两个数字串 S，T，使得 S 是 T 的前缀，则输出 NO ，否则输出 YES 。

请注意此处结果与输出的对应关系！

【输入样例】
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
【输出样例】
NO
YES
【提示】
数据范围：

对于 100% 的数据，1≤T≤40,1≤n≤10^4​​ 。

分析

1. 由于直接暴力逐个选两个字符串，时间复杂度n^2，会超时，使用Trie树，构造出这n个字符串，然后用一个judge函数进行判断；从1遍历到idx，找到一个完整字符串（cnt[i!=0]），然后看看以他最后一个字符结尾的结点，有没有孩子，有的话，说明这个串就可以当前缀就可以直接return true了；
2. 多组测试数据，初始化时候，就去全局变量逐个去看看哪些需要初始化，避免造成漏掉某个变量忘了初始化；

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int son[N][15];
int cnt[N], idx;  //cnt存储以每个节点（idx编号）结尾的单词数量
int t, n;
string s;

void add(string s) {
    
      
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
    
      
        int x = s[i] - '0';
        if (son[p][x] == 0) {
    
      
            //以p为根的结点不存在x这个孩子
            son[p][x] = ++idx;
        }
        p = son[p][x];
    }
    cnt[p]++;
}

//判断有没有某个串是另一个串的前缀
bool judge() {
    
      
    for (int i = 1; i <= idx; i++) {
    
      
        if (cnt[i] != 0) {
    
      
            //看看当前的串最后一个字符 有没有0-9这些字符的孩子
            for (int j = 0; j <= 9; j++) {
    
      
                if (son[i][j] != 0) {
    
      
                    return true;//有孩子
                }
            }
        }
    }
    return false;
}


int main() {
    
      
    cin.tie(0);
    cin >> t;
    while (t--) {
    
      
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
        cin >> n;
        for (int i = 0; i < n; ++i) {
    
      
            cin >> s;
            add(s);
        }
        if (judge())
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}