【数据结构】字典树

字典树板子

insert

nex[i][j] 表示连接从结点 p 引出的 c 的边连接的结点的编号，如果这个结点不存在，值就为 0

exist[i] 表示结点 i 是否为一个字符串的末尾

void insert(string s)
{
  	int p = 0;
    for (int i = 0; i < s.size(); i ++ )
    {
      	int c = s[i] - 'a'; // 字母转换成数字
      	if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      	p = nex[p][c]; // 指向下一位
    }
    exist[p] = 1;
}

find

bool find(string s)
{
    int p = 0;
    for (int i = 0; i < s.size(); i ++ )
    {
      	int c = s[i] - 'a'; // 字母转换成数字
      	if (!nex[p][c]) return 0; // 如果当前结点不存在，说明没有这样的字符串
      	p = nex[p][c]; // 指向下一位
    }
    return exist[p]; // 判断是否有以当前结点为末尾的字符串
}