POJ 3630 Phone List 解题报告

时间：2010-04-25 来源：MC_ACM

一、问题描述

题目大意：有n个电话号码（1<=n<=10000），每个电话号码由数字组成，长度为t(1<=t<=40).判断是否存在某个号码是其他某个号码的前缀，如果存在则输出“NO”，不存在则输出”YES”。

Sample Input

911

97625999

91125426

113

12340

123440

12345

98346

Sample Output

YES

二、解题思路

使用trie树，将号码一个一个地插入到trie树中。插入时如果发现该号码的前缀已经存在，或者发现插入号码成为其他号码的前缀，则返回false停止查找，输出“NO”。如果插入所有的号码都没有发现存在前缀或成为其他号码的前缀，则输出“YES”。

三、代码

#include<iostream>
using namespace std;
struct trieNode
{
    int next[10];
    bool isword;
};
trieNode Root;
int N=1000000;
trieNode tt[1000000];
int len;
bool insert(char * tar)
{
    trieNode * p= &tt[0];
    int id ;
    while(*tar)
    {
        id=*tar-'0';
        if(p->next[id]==-1)
        {
            p->next[id]=len;
            len++;
        }
        if(p->isword)//有前缀存在

            return false;
        p=&tt[p->next[id]];
        tar++;
    }
    p->isword=true;
    for(int i=0;i<10;++i)
    {
        //成为其他号码的前缀

        if(p->next[i]!=-1)
            return false;
    }
    return true;
}
void clear ( int n)
{
    for(int i=0;i<n;++i)
    {
        tt[i].isword=false;
        memset(tt[i].next,-1,sizeof(tt[i].next));
    }
}
int main()
{
    int c;
    int n;
    int i,j;
    char str[10005][15];
    scanf("%d",&c);
    clear(N);
    for(i=0;i<c;++i)
    {
        scanf("%d",&n);
        clear(len);
        len=1;
        bool flag=false;
        for(j=0;j<n;++j)
        {
            scanf("%s",&str[i]);
            if(flag)
                continue;
            if(insert(str[i])==false)
            {
                printf("NO\n");
                flag=true;
            }
        }
        if(!flag)
            printf("YES\n");
    }
    return 0;
}