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 字典树记录前缀出现次数

最新文章

热门文章