字典树

字典树

int k = 1;
int trie[1000000][26],col[1000000];
//插入算法
void insert(string& s)
{
	int len = s.length(), p = 0;
	for (int i = 0; i < len; i++)
	{
		int c = s[i] - 'a';
		if (trie[p][c]==0)
		{
			trie[p][c] = k;
			k++;
		}
		p = trie[p][c];
	}
	col[p] = 1;
}

//查找算法
int find(string& s)
{
	int len = s.length(), p = 0;
	for (int i = 0; i < len; i++)
	{
		int c = s[i] - 'a';
		if (trie[p][c] == 0)
			return 0;
		else
			p = trie[p][c];
	}
	if (col[p] == 1)
	{
		return 1;
	}
	return 0;
}

例题：

P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)