大家好，又见面了，我是全栈君。
一開始不知道这样的一维建树方法。
每次一层用一个链指向下一层最左边的结点，之后每一层用一个链表串联全部的结点，这样就建树成功了。
| 14328524 | 11732 | Accepted | C++ | 0.826 | 2014-10-09 13:13:14 |
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> pill;
const int nodemaxn = 4000 * 1000 + 100;
struct Trie{
int head[nodemaxn]; //左儿子链
int next[nodemaxn]; //右兄弟链
int ch[nodemaxn]; //这个结点代表的字符
LL tot[nodemaxn]; //有几个单词经过了这个结点
int sz; //结点个数
LL ret; //比較的次数
void clear(){
head[0] = 0; next[0] = 0; tot[0] = 0; sz = 1; ret = 0;
}
void insert(char *str){
int L = strlen(str);
int u = 0,v,found;
tot[0]++;
for(int i = 0; i <= L; i ++){
found = 0;
for(v = head[u]; v != 0 ; v = next[v]){ //到下一层去找
if(ch[v] == str[i]){
found = 1;
break;
}
}
if(!found){ //假设没有找到
v = sz ++;
tot[v] = 0;
ch[v] = str[i];
next[v] = head[u];
head[u] = v;
head[v] = 0;
}
u = v;
tot[u] ++;
}
}
void dfs(int u,int depth){
if(head[u] == 0){
ret += tot[u] * (tot[u] - 1) * depth;
}
else{
LL sum = 0;
for(int v = head[u] ; v != 0; v = next[v])
sum += tot[v] * (tot[u] - tot[v]);
ret += sum / 2 * (2 * depth + 1);
for(int v = head[u] ; v != 0; v = next[v])
dfs(v,depth + 1);
}
}
}trie;
const int maxn = 4000 + 10;
int main(){
int n,Case = 1;
while(scanf("%d",&n) && n){
trie.clear();
for(int i = 0; i < n; i++){
char str[maxn];
scanf("%s",str);
trie.insert(str);
}
trie.dfs(0,0);
printf("Case %d: %lld\n",Case++,trie.ret);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115603.html原文链接：https://javaforall.net
