hdu1671 字典树记录前缀出现次数

题意：
给你一堆电话号，问你这些电话号后面有没有相互冲突的，冲突的条件是当前这个电话号是另一个电话号的前缀，比如有 123456789 123,那么这两个电话号就冲突了，直接输出NO。

思路：

说白了就是前缀匹配，也就是以当前字符串为前缀的字符串有几个，只要有一个或者更多那么就直接NO了，快速的判断前缀的问题我们可以直接字典树记录前缀，先把所有的字符串都存在字典里，然后在枚举每一个，只要有一个是前缀（不算自己）那么就直接NO了，这里要注意一点，每次都要把Tree的内存清空，不然不同的mallco不释放，测试数据多了就MLE了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char str[10005][12];

typedef struct Tree
{
    Tree *next[10];
    int v;
}Tree;

Tree root;

void Buid_Tree(char *str)
{
    int len = strlen(str);
    Tree *p = &root ,*q;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - '0';
        if(p -> next[id] == NULL)
        {
            q = (Tree *) malloc(sizeof(root));
            q -> v = 1;
            for(int j = 0 ;j < 10 ;j ++)
            q -> next[j] = NULL;
            p -> next[id] = q;
            p = p -> next[id];
        }
        else
        {
            p = p -> next[id];
            p -> v ++;
        }
      }
}

int Find(char *str)
{
    int len = strlen(str);
    Tree *p = &root;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - '0';
        p = p -> next[id];
        if(p == NULL) return 0;
    }
    return p -> v;
}

bool solve(int n)
{
    for(int i = 1 ;i <= n ;i ++)
    if(Find(str[i]) != 1) return 0;
    return 1;
}

int dealTree(Tree* T)
{
    int i;
    if(T==NULL)
        return 0;
    for(i=0;i<10;i++)
    {
        if(T->next[i]!=NULL)
            dealTree(T->next[i]);
    }
    free(T);
    return 0;
}

int main ()
{
    int t ,n ,i;
    scanf("%d" ,&t);
    while(t--)
    {
         scanf("%d" ,&n);
         for(i = 0 ;i < 10 ;i ++)
         root.next[i] = NULL;
         for(i = 1 ;i <= n ;i ++)
         {
            scanf("%s" ,str[i]);
            Buid_Tree(str[i]);
         }
         if(solve(n)) puts("YES");
         else puts("NO");
         dealTree(&root);
      }
    return 0;
}

hdu1671 字典树记录前缀出现次数

相关推荐