UVa 11732 strcmp()函数(左孩子右兄弟表示法)

 #include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
using namespace std; const int maxn = * + ;
int n;
long long ans; struct Trie
{
int head[maxn]; //head[i]为第i个结点的左儿子编号
int next[maxn]; //next[i]为第i个结点的右兄弟编号
char ch[maxn]; //第i个结点上的字符
int tot[maxn];
int sz; void init()
{
sz = ;
head[] = tot[] = next[] = ;
} void insert(char *s)
{
int u = , v, n = strlen(s);
tot[]++;
for (int i = ; i <= n; i++)
{
bool found = false;
for (v = head[u]; v != ; v = next[v])
{
if (ch[v] == s[i])
{
found = true;
break;
}
}
if (!found)
{
v = sz++;
tot[v] = ;
ch[v] = s[i];
next[v] = head[u];
head[u] = v;
head[v] = ;
}
u = v;
tot[u]++;
}
} void dfs(int depth, int u)
{
if (head[u] == )
ans += tot[u] * (tot[u] - )*depth;
else
{
int sum = ;
for (int v = head[u]; v != ; v = next[v])
sum += tot[v] * (tot[u] - tot[v]);
ans += sum / * ( * depth + );
for (int v = head[u]; v != ; v = next[v])
dfs(depth + , v);
}
}
}t; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
char str[];
int kase = ;
while (~scanf("%d", &n), n)
{
t.init();
while (n--)
{
scanf("%s", str);
t.insert(str);
}
ans = ;
t.dfs(,);
printf("Case %d: %lld\n", ++kase, ans);
}
return ;
}
上一篇:Codeforces Round #528 Div. 1 自闭记


下一篇:jsp之jsp基础