字符串-字典树

淩亂°似流年 2022-12-06 04:03 27阅读 0赞

### 文章目录 ###

*  字典树
 *  例题
 *   *  HDU-1251统计难题
     *  POJ-3603Phone List
     *  AcWing-143最大异或对
     *  HDU-5536Chip Factory

# 字典树 #

--------------------

字典树(Trie)，顾名思义是以树结构来模拟字典。回想我们查字典的过程，比如查找"man"，先翻到字典m部分，再翻第二个字母a和第三个字母n，一共查找3次。查找次数最多是等于个单词的长度。插入查找单词的时间复杂度时 O ( m ) O(m) O(m)，此外有公共前缀的单词只需存一次公共前缀，节省了空间，也可理解为前缀树。

根结点不包含字符，根结点外每个结点包含一个字符，从根结点到某子结点路径上经过的字符，连起来就是该结点对应的字符串，每个结点的字符串互不相同。  
如图所示是单词hi，he，heat，man，may的字典树。代码实现时会在结点设标识表示是否为单词结尾，如图中下划线。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]  
字典树应用

1.  字符串检索  
    查询检索字符串
2.  词频统计  
    统计一个单词出现了多少次
3.  字符串排序  
    字典树建好后，先序遍历就得到了排序。
4.  前缀匹配  
    根据前缀，用于搜索提示等

# 例题 #

--------------------

## HDU-1251统计难题 ##

[HDU-1251统计难题][HDU-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

**分析：**  
字典树模板题，将单词全部插入字典树，维护经过次数 n u m \[ \] num\[\] num\[\]，再输出前缀单词对应经过次数即可。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1000006;
    int trie[maxn][26]; //26叉字典树，存储值为对应子节点位置(编号)
    int num[maxn] = {  0 }; //某前缀单词的数量
    int pos = 1; //新分配的存储位置，可理解为结点编号
    void insert(char s[]) {  //向字典树插入单词
        int p = 0; //从根结点开始
        for (int i = 0; s[i]; i++) { 
            int n = s[i] - 'a';
            if (trie[p][n] == 0) //对应字符还没有值则新分配
                trie[p][n] = pos++;
            p = trie[p][n];
            num[p]++;
        }
    }
    int find(char s[]) {   //返回某字串为前缀的单词数量
        int p = 0;
        for (int i = 0; s[i]; i++) { 
            int n = s[i] - 'a';
            if (trie[p][n] == 0)
                return 0;
            p = trie[p][n];
        }
        return num[p];
    }
    int main(){ 
        char s[15];
        while (gets(s) && s[0] != '\0')
            insert(s);
        while (~scanf("%s", s))
            printf("%d\n", find(s));
        return 0;
    }

## POJ-3603Phone List ##

[POJ-3603Phone List][]

> 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:  
> Emergency 911  
> Alice 97 625 999  
> 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

**分析：**  
给若干字符串，问某字符串是否是另一字符串的前缀。依次将字符串插入字典树中并在末尾标记，当插入过程中遇到标记时，则说明遇到了它的前缀字串；否则检查是否有新分配存储位置 p o s pos pos，若没有新分配，则说明它是其它字串的前缀。

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 100005;
    int trie[maxn][10]; //0~9即十叉字典树
    bool flag[maxn];//标记
    int pos;
    char s[20];
    bool insert() { 
        int p = 0;
        bool isNew = false;
        for (int i = 0; s[i]; i++) { 
            int u = s[i] - '0';
            if (trie[p][u] == 0) { 
                trie[p][u] = pos++;
                isNew = true;
            }
            p = trie[p][u];
            if (flag[p])return false; //经过标记
        }
        flag[p] = true;
        return isNew;//没经过标记但处在其他串路径上
    }
    int main() { 
        int t, n;
        scanf("%d", &t);
        while (t--) { 
            memset(flag, false, sizeof(flag));
            memset(trie, 0, sizeof(trie));
            bool ans = true;
            pos = 1;
            scanf("%d", &n);
            for (int i = 0; i < n; i++) { 
                scanf("%s", s);
                if (ans && !insert())
                    ans = false;
            }
            if (ans)puts("YES");
            else puts("NO");
        }
        return 0;
    }

## AcWing-143最大异或对 ##

[AcWing-143最大异或对][AcWing-143]

> 在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？  
> **输入格式**  
> 第一行输入一个整数N。  
> 第二行输入N个整数A1～AN。  
> **输出格式**  
> 输出一个整数表示答案。  
> **数据范围**  
> 1≤N≤105,  
> 0≤Ai<231  
> **输入样例：**  
> 3  
> 1 2 3  
> **输出样例：**  
> 3

**分析：**  
求最大异或值，构建二叉字典树(01)，把数字转换成二进制，从高位往地位，决策使路径尽可能不同（不同异或值才为1），遍历输出最优解。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100005;
    int trie[maxn * 100][2], num[maxn * 100];
    int a[maxn], pos = 1;
    void insert(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) { 
            int u = x >> i & 1;
            if (trie[p][u] == 0)
                trie[p][u] = pos++;
            p = trie[p][u];
        }
        num[p] = x;//结尾标记这条路对应的数值
    }
    int find(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) { 
            int u = x >> i & 1;
            if (trie[p][!u])p = trie[p][!u];//另一条路可以走
            else p = trie[p][u];//不能走则走相同的
        }
        return num[p] ^ x;
    }
    int main() { 
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) { 
            cin >> a[i];
            insert(a[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, find(a[i]));
        cout << ans << "\n";
        return 0;
    }

## HDU-5536Chip Factory ##

[HDU-5536Chip Factory][]

> **Problem Description**  
> John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip produced this day has a serial number si.  
> At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below:  
> maxi,j,k(si+sj)⊕sk  
> which i,j,k are three different integers between 1 and n. And ⊕ is symbol of bitwise XOR.  
> Can you help John calculate the checksum number of today?  
> **Input**  
> The first line of input contains an integer T indicating the total number of test cases.  
> The first line of each test case is an integer n, indicating the number of chips produced today. The next line has n integers s1,s2,…,sn, separated with single space, indicating serial number of each chip.  
> 1≤T≤1000  
> 3≤n≤1000  
> 0≤si≤109  
> There are at most 10 testcases with n>100  
> **Output**  
> For each test case, please output an integer indicating the checksum number in a line.  
> **Sample Input**  
> 2  
> 3  
> 1 2 3  
> 3  
> 100 200 300  
> **Sample Output**  
> 6  
> 400

**分析：**  
给定一个序列 s s s，要求找到三个不同的 i , j , k i,j,k i,j,k，使得 ( s \[ i \] + s \[ j \] ) (s\[i\]+s\[j\]) (s\[i\]\+s\[j\]) xor  s \[ k \] s\[k\] s\[k\]的值最大。  
类似上一题最大异或对，遍历 i , j i,j i,j，因为 i j k ijk ijk要不同，所以要先删掉 s \[ i \] 、 s \[ j \] s\[i\]、s\[j\] s\[i\]、s\[j\]，然后查询 s \[ i \] + s \[ j \] s\[i\]+s\[j\] s\[i\]\+s\[j\]，也是决策使路径尽量不同，更新最优解，然后回溯插入删掉的 s \[ i \] 、 s \[ j \] s\[i\]、s\[j\] s\[i\]、s\[j\]。  
至于怎么删，其实插入时是 c n t \[ \] cnt\[\] cnt\[\]\++记录路径，删掉改成 c n t \[ \] cnt\[\] cnt\[\]–即可。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 40004;
    int trie[maxn][2], cnt[maxn], num[maxn];
    int pos, k, a[1003];
    void insert(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) { 
            int u = x >> i & 1;
            if (trie[p][u] == 0)
                trie[p][u] = pos++;
            p = trie[p][u];
            cnt[p]++;   //记录经过路径
        }
        num[p] = x;
    }
    void del(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) { 
            int u = x >> i & 1;
            p = trie[p][u];
            cnt[p]--;   //对应路径--
        }
    }
    int find(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) { 
            int u = x >> i & 1;
            //因为存在trie[p][!u]不为空(已分配位置)，但是其路径已经删除了，所以不能用其判断
            //应该用cnt判断，这点和上一题不同
            if (cnt[trie[p][!u]])p = trie[p][!u];//优先选另一条路
            else p = trie[p][u];
        }
        return num[p] ^ x;
    }
    int main() { 
        int t, n;
        cin >> t;
        while (t--) { 
            memset(cnt, 0, sizeof(cnt));
            memset(num, 0, sizeof(num));
            memset(trie, 0, sizeof(trie));
            pos = 1;
            cin >> n;
            for (int i = 0; i < n; i++) { 
                cin >> a[i];    //插入进字典树
                insert(a[i]);
            }
            int ans = 0;
            for (int i = 0; i < n; i++) //遍历ij
                for (int j = i + 1; j < n; j++) { 
                    del(a[i]);  //删除ij
                    del(a[j]);
                    ans = max(ans, find(a[i] + a[j]));
                    insert(a[i]); //插入ij回溯
                    insert(a[j]);
                }
            cout << ans << "\n";
        }
        return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1ff461bcc20342cbb5e40a619c1fbb9c.png
[HDU-1251]: https://vjudge.net/problem/HDU-1251
[POJ-3603Phone List]: https://vjudge.net/problem/POJ-3630
[AcWing-143]: https://www.acwing.com/problem/content/145/
[HDU-5536Chip Factory]: https://vjudge.net/problem/HDU-5536
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708