HDU-1671-Phone List(字典树)

Phone List

字符串集合中的字符串都不能是字符串其他集合的前缀

#include<bits/stdc++.h>
using namespace std;
int tree[100100][11];
int pos;
int num[100100];
string s[100100];
void init( )
{
    pos=1;
    memset(num,0,sizeof(num));
    memset(tree,0,sizeof(tree));
}
void insert(string s)
{
    int len=s.size( );
    int root =0;
    for(int i=0;i<len;i++)
    {
        int x=s[i]-'0';
        if(!tree[root][x])
        {
            tree[root][x]=pos++;
        }
        root=tree[root][x];
        num[root]++;
    }
}
bool judgepremix(string s)
{
    int len=s.size( );
    int root=0;
    for(int i=0;i<len;i++)
    {
        int x=s[i]-'0';
        root=tree[root][x];
        if(num[root]==1)
        {
            return 1;
        }
    }
    return 0;
}
int main( )
{
    int t,n;
    cin>>t;
    while(t--)
    {
        init( );
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            insert(s[i]);
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            if(!judgepremix(s[i]))
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}