poj3630字典树应用找字符串中有没另一个字符串的前缀

题目链接

Phone List

题目描述（Description)

给出一列电话号码，判断这些号码里时候有的号码是另一个号码的前缀，如果是，则此号码不符合条件（输出NO），否则输出YES。

分析(Analysis)

属于字典树的应用。这里的branch是0-9这10个字符。设置flag作为判断的标志。

分两步：

• 当前插入单词word是否为之前字符串的前缀
• 之前的字符串是否为word的前缀

代码(Code)

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100001;
const int branch=10;
struct tree_node{
    bool end;
    tree_node *next[branch];
}root,node[maxn];
int p;
bool flag;
void insert(char *word)
{
    tree_node *location=&root;
    bool newflag=false;
    while(*word){
        if(location->end)//前面的串是word的前缀 
        {
            flag=false;
            return;    
        }
        if(location->next[*word-'0']==NULL){//建立新的分支，word不是之前串的前缀 
            newflag=true;
            node[p].end=false;
            memset(node[p].next,NULL,sizeof(node[p].next));
            location->next[*word-'0']=&node[p++];
        }
        location=location->next[*word-'0'];
        word++;
    }
    location->end=true; 
    if(!newflag)//word是之前串的前缀 
        flag=false;
}
int main()
{
    int t,n;
    char s[11];
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        p=0;
        flag=true;
        memset(root.next,NULL,sizeof(root.next));
        while(n--){
            scanf("%s",s);
            if(flag)//没有出现一个字符串是另一个字符串的前缀的情况下插入字典树 
                insert(s);
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}