[HIHO1107]Shortest Proper Prefix(trie)

时间:2023-12-31 20:04:50

题目链接:http://hihocoder.com/problemset/problem/1107

题意:求有多少非依赖前缀,使得前缀下标识的字符串不超过5个。

这里非依赖的意思是,假如前缀a,b,a是b的前缀,则b依赖于a。假如a下标识的字符串已经不超过5个了,那么b就不能统计了。

trie树直接搞,遇到<=5的前缀就计数,否则递归一层。

写了一种非指针的trie树,val存值,id存某一层某一个节点的下一个节点的id。sz维护接下来要插入的id。

 #include <bits/stdc++.h>
using namespace std; const int maxn = ;
const int maxm = ;
const int maxc = ;
typedef struct Trie {
int root, sz;
int val[maxm], id[maxm][maxc];
void build() {
root = ; sz = ;
memset(val, , sizeof(val));
memset(id, -, sizeof(id));
val[root] = 0x7f7f7f7;
}
void insert(const char* str) {
int len = strlen(str);
int u = root;
for(int i = ; str[i]; i++) {
int v = str[i] - 'a';
if(id[u][v] == -) id[u][v] = ++sz;
u = id[u][v];
val[u]++;
}
}
int dfs(int u) {
if(val[u] <= ) return ;
int ret = ;
for(int i = ; i < ; i++) {
if(id[u][i] != -) {
ret += dfs(id[u][i]);
}
}
return ret;
}
}Trie; int n;
Trie trie;
char tmp[maxm]; int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
trie.build();
for(int i = ; i < n; i++) {
scanf("%s", tmp);
trie.insert(tmp);
}
printf("%d\n", trie.dfs(trie.root));
}
return ;
}