F - phone list HDU - 1671 (dictionary tree prefix)

The question ： Give you a list of phone numbers to see if there is a prefix for other numbers .

analysis ： To judge the prefix, we only need to see whether the previous string is the prefix of the existing string or the prefix of the following string .

（1） The prefix of the string has appeared . use flag Represents whether a word ending in this node appears ;

（2） use sum Represents the number of words prefixed by the end of the node , Add judgment conditions in the middle .

#include<iostream>
#include<cstdio>
#include<map>
#include<string.h>
#include<cstring>
using namespace std;
const int maxn = 100010;
string a, b;
int trie[maxn][12], tot;
int m, rt, t, flag[maxn], ans, sum[maxn];


void insertit(int rt, string str)
{
    int len = str.size();
    for(int i = 0; i < len; i++)
    {
        int x = str[i] - '0';
        if(trie[rt][x] == 0) trie[rt][x] = ++tot;
        rt = trie[rt][x];
        if(flag[rt]) ans = 1;
        sum[rt]++;
    }
    if(sum[rt] > 1) ans = 1;
    flag[rt]++;
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        rt = 1; tot = 1;
        scanf("%d", &m);
        ans = 0;
        while(m--)
        {
            cin >> a;
            insertit(rt, a);
        }
        if(ans) puts("NO");
        else puts("YES");
        memset(flag, 0 ,sizeof(flag));
        memset(trie, 0, sizeof(trie));
        memset(sum, 0, sizeof(sum));
    }
    return 0;
}