Trie

Trie

#include <iostream>
#include <cstdio>
#include <cstring>

int trie[100005][31], tot = 1; // 初始化， 且假设字符串均只由小写字母构成
bool end[100005]; // 是否是一个字符串的结尾

void Insert(char* s) // 插入一个字符串
{
    int len = strlen(s), p = 1; // p为节点编号， 注意一定要从1开始， 0代表没有这个节点

    for(int i = 0; i < len; i ++)
    {
        int ch = s[i] - 'a';

        if(trie[p][ch] == 0) trie[p][ch] = ++ tot;

        p = trie[p][ch];
    }

    end[p] = true;
}

bool Search(char* s) // 查找一个字符串是否出现过
{
    int len = strlen(s), p = 1;

    for(int i = 0; i < len; i ++)
    {
        int ch = s[i] - 'a';

        p = trie[p][ch];

        if(!p) return false;
    }

    return end[p];
}

int main()
{

}