ACM 字典树 Phone List & Hat’s Words

港控/mmm° 2022-06-12 09:42 173阅读 0赞

**字典树：**又称单词查找树，[Trie树][Trie]，是一种[树形结构][Link 1]，是一种哈希树的变种。

**典型应用：**统计，排序和保存大量的[字符][Link 2]串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

**优点：**利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比[哈希][Link 3]树高。

**基本性质：**

1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。  
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。  
3.每个节点的所有子节点包含的字符都不相同。

**基本模板:**(来自百度百科)

#define MAX 26//字符集大小
    typedef struct TrieNode
    {
        int nCount;//记录该字符出现次数
        struct TrieNode* next[MAX];
    }TrieNode;
     
    TrieNode Memory[1000000];
    int allocp=0;
     
    /*初始化*/
    void InitTrieRoot(TrieNode* *pRoot)
    {
        *pRoot=NULL;
    }
     
    /*创建新结点*/
    TrieNode* CreateTrieNode()
    {
        int i;
        TrieNode *p;
        p=&Memory[allocp++];
        p->nCount=1;
        for(i=0;i<MAX;i++)
        {
            p->next[i]=NULL;
        }
        return p;
    }
     
    /*插入*/
    void InsertTrie(TrieNode* *pRoot,char *s)
    {
        int i,k;
        TrieNode*p;
        if(!(p=*pRoot))
        {
            p=*pRoot=CreateTrieNode();
        }
        i=0;
        while(s[i])
        {
            k=s[i++]-'a';//确定branch
            if(!p->next[k])
                p->next[k]=CreateTrieNode();
                    else
                p->next[k]->nCount++;
            p=p->next[k];
        }
    }
     
    //查找
    int SearchTrie(TrieNode* *pRoot,char *s)
    {
        TrieNode *p;
        int i,k;
        if(!(p=*pRoot))
        {
            return0;
        }
        i=0;
        while(s[i])
        {
            k=s[i++]-'a';
            if(p->next[k]==NULL) return 0;
            p=p->next[k];
        }
        return p->nCount;
    }

**HDU 1671 Phone List**

**![20170720221601813][]**

**![20170720221610429][]**

题目大意：（例题带入）有2组数据，第一组数据有3个电话号码，问是否存在一个号码是另一个的前缀，若存在则不合适，输出NO。

思路:字典树，在建树的时候直接判断了...

#include <iostream>
    #define MAX 10
    using namespace std;
    bool flag;
    typedef struct Trie_Node
    {
        bool isphone;
        struct Trie_Node *next[MAX];    
    }Trie;
    void insert(Trie *root,char *phone)
    {
        Trie *p=root;
        while(*phone!='\0')
        {
            if(p->next[*phone-48]==NULL)
            {
                Trie *temp=(Trie *)malloc(sizeof(Trie));
                temp->isphone=false;
                for(int i=0;i<MAX;i++)
                temp->next[i]=NULL;
                p->next[*phone-48]=temp;    
            }
            if(p->isphone==true)
            flag=true;
            p=p->next[*phone-48];
            phone++;
        }
        p->isphone=true;
        for(int i=0;i<MAX;i++)
        {
            if(p->next[i]!=NULL)
            {
                flag=true;
                break;
            }
        }    
    }
    void del(Trie *root)
    {
        for(int i=0;i<MAX;i++)
        {
            if(root->next[i]!=NULL)
            del(root->next[i]);
        }
        free(root);
    }
    int main(int argc, char *argv[])
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int i;
            int n;
            char phone[11];
            Trie *root=(Trie *)malloc(sizeof(Trie));
            root->isphone=false;
            flag=false;
            for(i=0;i<MAX;i++)
            root->next[i]=NULL;
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%s",phone);
                if(flag!=true)
                insert(root,phone);
            }
            if(flag==true)
            printf("NO\n");
            else
            printf("YES\n");
            del(root);               
        }
        return 0;
    }

**HDU 1247 Hat’s Words**

**![20170720221919551][]**

题目大意：输入直到EOF结束，判断是否存在两个组合可以组成另一个字符串。

思路：先把所有字符串都存下来建树，然后从根走到每个叶子结点记下来比较。

#include<iostream>
    #include<string.h>
    #include<stdlib.h>
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int MAX=26;
    typedef struct Trie_Node
    {
        bool isWord;
        struct Trie_Node *next[MAX];
    }Trie;
    char s[50010][50];
    void insert(Trie *root,char *word)
    {
        Trie *p=root;
        int i=0;
        while(word[i]!='\0')
        {
            if(p->next[word[i]-'a']==NULL)
            {
                Trie *temp=(Trie *)malloc(sizeof(Trie));
                for(int j=0;j<MAX;j++)
                 temp->next[j]=NULL;
                temp->isWord=false;
                p->next[word[i]-'a']=temp;
            }
            p=p->next[word[i]-'a'];
            i++;
        }
        p->isWord=true;
    }
    bool search(Trie *root,char *word)
    {
        Trie *p=root;
        for(int i=0;word[i]!='\0';i++)
        {
            if(p->next[word[i]-'a']==NULL)
              return false;
            p=p->next[word[i]-'a'];
        }
        return p->isWord;
    }
    void del(Trie *root)
    {
        for(int i=0;i<MAX;i++)
        {
            if(root->next[i]!=NULL)
              del(root->next[i]);
        }
        free(root);
    }
    int main()
    {
        int i,j;
        int cnt=0;
        char str[50];
        Trie *root=(Trie *)malloc(sizeof(Trie));
        for(i=0;i<MAX;i++)
        root->next[i]=NULL;
        root->isWord=false;
        while(scanf("%s",s[cnt])!=EOF)
        {
            insert(root,s[cnt++]);
        }
        for(i=0;i<cnt;i++)
        {
            int len=strlen(s[i]);
            for(j=1;j<len-1;j++)
            {
                char temp1[50]={'\0'};
                char temp2[50]={'\0'};
                strncpy(temp1,s[i],j);
                strncpy(temp2,s[i]+j,len-j);
                if(search(root,temp1)&&search(root,temp2))
                {
                    printf("%s\n",s[i]);
                    break;
                }
            }
        }
        del(root);
        return 0;
    }

[Trie]: https://baike.baidu.com/item/Trie%E6%A0%91
[Link 1]: https://baike.baidu.com/item/%E6%A0%91%E5%BD%A2%E7%BB%93%E6%9E%84
[Link 2]: https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6
[Link 3]: https://baike.baidu.com/item/%E5%93%88%E5%B8%8C
[20170720221601813]: /images/20220612/39ceef73b1044a4c98a64df282d7d799.png
[20170720221610429]: /images/20220612/6285f73bf3624836a56955f3d1abd49e.png
[20170720221919551]: /images/20220612/362da4d1a49f47d687ba70867d942142.png