字符串-Trie(字典树)-1—算法—6.23

手搓代码理解：

/**
 * ClassName: ${NAME}
 * package: ${PACKAGE_NAME}
 * Description:
 * @Author: innno
 * @Create: 2024/2/27 - 21:54
 * @Version: v1.0
 */
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll MAX = 1e5;

class Trie
    {
        ll idx = 0;//idx为下标，即当前移动的位置
        ll cnt[MAX]{};//cnt为标记数组，值为0/非0，用于表示一个字符串的结束位置
        ll tr[MAX][26]{};//存储本体，第一维用于存当前的位置，即idx，第二维用于存当前位置有哪些字母后继，值为后继位置
    public:
        Trie() = default;

        ~Trie() = default;

        void insert(string &str);//插入函数

        bool search(string &str);//查询函数
    };

void Trie::insert(string &str)
    {
        ll p = 0;//当前运行到的位置
        for (auto &ch: str)
            {
                ll x = ch - 'a';//查询于‘a’的相对位置，便于存放在tr数组的第二维
                if (tr[p][x] == 0)tr[p][x] = ++idx;//判别当前位置是否有值，若没有，则创建一个位置，并把位置作为值赋予
                p = tr[p][x];//算法关键，使p进行到所需位置上，以便下一次循环跳转
            }
        cnt[p]++;//记录结束位置
    }

bool Trie::search(string &str)//与插入函数结构一样
    {
        ll p = 0;
        for (auto &ch: str)
            {
                ll x = ch - 'a';
                if (tr[p][x] == 0)return false;//如果没有某值，则返回0
                p = tr[p][x];//跳转
            }
        return cnt[p];//找到位置，但是根据cnt的值返回，若cnt为0，说明有该结尾，但是没有该字符串，若为1，说明查找成功
    }

Trie Tr;

int main()
    {
        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        ll i = 5;
        while (i--)
            {
                ll n;
                cin >> n;
                string str;
                cin >> str;
                if (n == 0)Tr.insert(str);
                else
                    {
                        Tr.search(str) ? cout << "True" : cout << "false";
                    }
            }
        return 0;
    }