Aczy156

Algorithm1.2 字符串数据结构 Trie树

[TOC]

字符串 数据结构 Trie树

工程开发中的应用：浏览器的搜索框内容提示功能

demo：Trie树维护的字典：[he, his, hers, she]，要从字典里查到的单词：ahishers

构建Trie树：

  • node节点结构体：
    • 当前节点的值
    • 存放指向下一层node节点指针的List（最多26个=>26个字母）
  • bool数组：标记某一个节点是否是尾部节点【例如下图中的trie树双层圈的都是】

image-20211026101023351

通过root往下查询某一个待测字串：

  • 查找正确：
    • 到双层圈的节点 => 完成完全匹配
    • 未到双层圈的节点 => 完成部分(前缀)匹配
  • 查找错误：
    • 空指针 => 直接从root根节点就无法匹配
    • 未找到双层圈的节点 => 完成部分(前缀)匹配

[模版] 点名问题

https://www.luogu.com.cn/problem/P2580

题目大意：给出若干个人的名字，多次询问看某个询问是否是第一次出现 & 重复出现【字典树最基本的应用】 & 错误名字

1、数据结构：

ch[maxn][字符串的涉及字符空间]，一般字典树第二维都是26，26个字母

val[maxn]用来记录索引到这个点的值，例如学生名字是索引的字典，这个学生的各个成绩就是val这个值，exist[maxn]用来记录是否存在或者重复访问

2、常用操作：

插入insert：

查找query：

  • 是否存在或者重复访问，访问exist数组
  • 字符串对应的值，访问val数组

AC代码：只需访问exist，看是否存在或者重复访问

#include <iostream>
using namespace std;
#include <cstring>
#define maxn 500010
struct trie {
    int nex[maxn][26], cnt; 
    int exist[maxn]; // 0 没出现；1 第一出现；2 重复出现
 		int val[maxn]; // -1 查不到这个人的对应的值
  	void insert(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;
            p = nex[p][c];
        }
        // 修改val数组的地方
    }
    int find(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
      	// 修改exist数组的地方
        if (!exist[p]) {exist[p] = 1;return 1;}
        return 2;
    }
  	int getvalue(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return -1;
            p = nex[p][c];
        }
        return val[p];
    }
}tree;
int n, m;
char s[55];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s);
        tree.insert(s);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%s", s);
        switch (tree.find(s)) {
            case 0: printf("WRONG\n");break;
            case 1: printf("OK\n");break;
            case 2: printf("REPEAT\n");break;
        }
    }
    return 0;
}
Posted on Feb 1, 2021