蓝桥杯算法提高VIP-不同单词个数统计(字典树)----momoc

解题思路:
使用字典树来解。

字典树传送门。

https://blog.csdn.net/qq_38891827/article/details/80532462

注意事项:

    边插入边统计，如果当前字符串结尾下标已经被标记，就不对答案做贡献，否则ans++.
参考代码:

#include <bits/stdc++.h>
using namespace std;
const int N =2e5+5;
unsigned tree[N][30];
bool flag[N] = {0};
int tot;
int ans = 0;
void insert(char *str){
	int len = strlen(str);
	int root = 0;
	for(int i=0;i<len;i++){
		int id = str[i] - 'a';
		if(!tree[root][id]) tree[root][id] = ++tot;
		root = tree[root][id];
	}
	if(flag[root]==1 ) {
		return ;
	}
	flag[root] = 1;
	ans++;
}
int main ()
{	
	char s[101];
	tot = 0;
	while(scanf("%s",s)!=EOF){
		insert(s);
	}
	
	cout<<ans<<endl;
	return 0;
}