【字典树】

HDU 1251 

http://acm.hdu.edu.cn/showproblem.php?pid=1251

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

 

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

 

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

 

Sample Input

banana band bee absolute acm ba b band abc

 

Sample Output

2 3 1 0

 

题意：一组字符串中某前缀出现次数

代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
struct node
{
    int cnt;
    node *next[27];
}*root;
void Maketree(char *str)
{
    node *p, *q;
    p=root;
    int len=strlen(str);
    for(int i=0; i<len; i++)
    {
        int ans=str[i]-'a';
        if(p->next[ans]!=NULL)
        {
            p=p->next[ans]; p->cnt++;
        }
        else
        {
            q=new node;
            for(int j=0; j<26; j++)
                q->next[j]=NULL;
            p->next[ans]=q; p=q; p->cnt=1;
        }
    }
}
int Findtree(char *str)
{
    node *p;
    p=root;
    for(int i=0; i<strlen(str); i++)
    {
        int ans=str[i]-'a';
        if(p->next[ans]==NULL)
            return 0;
        p=p->next[ans];
    }
    return p->cnt;
}
void Deletetree(node *root)
{
    if(root==NULL) return ;
    for(int i=0; i<26; i++)
    {
        if(root->next[i]!=NULL)
            Deletetree(root->next[i]);
    }
    delete root;
    root=NULL;
}
int main()
{
    root=new node;
    for(int i=0; i<26; i++)
        root->next[i]=NULL;
    root->cnt=0;
    char str1[15];
    while(gets(str1)!=NULL)
    {
        if(strlen(str1)==0)
            break;
        Maketree(str1);
    }
    while(scanf("%s", str1)!=EOF)
    {
        if(strlen(str1)==0)
            break;
        printf("%d\n", Findtree(str1));
    }
    return 0;
}

 HDU 1671 Phone List

http://acm.hdu.edu.cn/showproblem.php?pid=1671

Problem Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

 

Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

 

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

 

Sample Input

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

 

Sample Output

NO

YES

 

解题思路：

找一个串是否为一个串的前缀，有的话输出NO,else 输出YES
当不是释放内存的时候会mtl;将每个串的结尾标记为-1,那么判断这个串有前面的串为其
前缀，还要判断这个串是否为前面串的前缀；

代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
struct node
{
    int cnt;
    node *next[11];
}*root;
int Maketree(char *str)
{
    node *p, *q;
    p=root;
    int flag=0;
    int len=strlen(str);
    for(int i=0; i<len; i++)
    {
        int ans=str[i]-'0';
        if(p->next[ans]!=NULL)
        {
            p=p->next[ans];
            if(p->cnt==1)
                flag=1;
        }
        else
        {
            q=new node;
            for(int j=0; j<10; j++)
                q->next[j]=NULL;
            p->next[ans]=q; p=q; p->cnt=0;
        }
        if(i==len-1)
            p->cnt=1;
    }
    for(int i=0; i<10; i++)
        if(p->next[i]!=NULL)
            flag=1;
    return flag;
}
void Deletetree(node *root)
{
    if(root==NULL) return ;
    for(int i=0; i<10; i++)
    {
        if(root->next[i]!=NULL)
            Deletetree(root->next[i]);
    }
    delete root;
    root=NULL;
}
int main()
{
    int T, n;
    char str1[15];
    scanf("%d", &T);
    while(T--)
    {
        root=new node;
        for(int i=0; i<10; i++)
            root->next[i]=NULL;
        root->cnt=0;
        scanf("%d", &n);
        int flag2=0, flag1=0;
        for(int i=0; i<n; i++)
        {
            scanf("%s", str1);
            int flag1=Maketree(str1);
            if(flag1==1&&i!=0)
                flag2=1;
        }
        if(flag2)
            printf("NO\n");
        else
            printf("YES\n");
        Deletetree(root);
    }
    return 0;
}