[複習][HDU1671]字典樹（trie樹）phone list

題目背景

HDU1671

題目描述

給出一份電話号碼清單，如果不存在有一個号碼是另一個号碼的字首，我們就說這份電話号碼清單是合法的。讓我們看看如下号碼清單：

1. Emergency 911

2. Alice 97625999

3. Bob 91125426

在這組号碼中，我們不能撥通 Bob 的電話，因為當你按下 Bob 電話号碼的前 3 個數字“911”時，電話局會把你的撥接上網到 Emergency 的線路。

是以這組号碼是不合法的。

輸入格式

有多組輸入資料。

第一行輸入一個正整數 t（1<=t<=40），表示資料組數。

每組資料第一行是一個正整數 n（1<=n<=10000），表示電話号碼的數量。

接下來有 n 行，每行一個電話号碼，每個電話号碼是不超過 10 位的連續數字。

輸出格式

對每組資料，如果電話号碼清單合法，則輸出“YES”，不合法則輸出“NO”。

樣例資料

輸入

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

輸出

NO

YES

分析： trie樹模闆

代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;

int getint()
{
    int sum=,f=;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-;
        ch=getchar();
    }
    for(;ch>='0'&&ch<='9';ch=getchar())
        sum=(sum<<)+(sum<<)+ch-;
    return sum*f;
}

struct node{
    int son[];
    int num;
}trie[];
char s[];
int tot=,top=;
int n,t,a[];

void build_trie()
{
    int position=;
    int len=strlen(s);
    for(int i=;i<len;++i)
    {
        if(!trie[position].son[s[i]-'0'])
        {
            trie[position].son[s[i]-'0']=++tot;
        }
        position=trie[position].son[s[i]-'0'];
        trie[position].num++;
    }

    a[++top]=position;
}

int main()
{
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);

    t=getint();
    while(t--)
    {
        memset(trie,,sizeof(trie));
        memset(a,,sizeof(a));
        top=;tot=;
        bool sign=;
        n=getint();
        for(int i=;i<=n;++i)
        {
            scanf("%s",s);
            build_trie();
        }

        for(int i=;i<=n;++i)
        {
            if(trie[a[i]].num>)
                sign=;
        }

        if(sign)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }

    return ;
}
           

本題結。