这道题也是卡了挺久的。
给出一个字符串比较的算法，有n个字符串两两比较一次，问一共会有多少次比较。
因为节点会很多，所以Tire树采用了左儿子右兄弟的表示法来节省空间。
假设两个不相等的字符串的最长公共前缀的长度为i，那么比较次数应该是2i+1。
如果两个字符串相等，比较次数则是2i+2.
可以像大白书上一样先构建好Tire树，然后DFS统计答案。
#include <cstdio>
#include <cstring> const int maxnode = * + ; struct Tire
{
int sz;
int son[maxnode], bro[maxnode], tot[maxnode];
char ch[maxnode];
long long ans;
void clear() { sz = ; son[] = bro[] = tot[] = ; } void insert(char* s)
{
int u = , v, n = strlen(s);
tot[]++;
for(int i = ; i <= n; i++)
{
bool found = false;
for(v = son[u]; v; v = bro[v])
if(ch[v] == s[i]) { found = true; break; }
if(!found)
{
v = sz++;
son[v] = ;
bro[v] = son[u];
son[u] = v;
tot[v] = ;
ch[v] = s[i];
}
u = v;
tot[u]++;
}
} void dfs(int d, int u)
{
if(son[u] == ) { ans += tot[u] * (tot[u]-) * d; return; }//叶节点
long long sum = ;
for(int v = son[u]; v; v = bro[v])
sum += tot[v] * (tot[u] - tot[v]);
ans += sum / * (d * + );
for(int v = son[u]; v; v = bro[v]) dfs(d+, v);
} long long count()
{
ans = ;
dfs(, );
return ans;
}
}tire; const int maxl = + ;
char s[maxl]; int main()
{
//freopen("in.txt", "r", stdin); int n, kase = ;
while(scanf("%d", &n) == && n)
{
tire.clear();
for(int i = ; i < n; i++) { scanf("%s", s); tire.insert(s); }
printf("Case %d: %lld\n", ++kase, tire.count());
} return ;
}
代码君
也可以边插入字符串边统计，代码更短，而且速度也更快。这种做法是从某位菊苣的博客中看到的。
#include <cstdio>
#include <cstring> const int maxnode = * + ; long long ans; struct Tire
{
int son[maxnode], bro[maxnode], tot[maxnode];
char ch[maxnode];
int sz;
void clear() { sz = ; son[] = bro[] = tot[] = ; } void insert(char* s)
{
int u = , v, n = strlen(s);
tot[]++;
for(int i = ; i <= n; i++)
{
bool found = false;
for(v = son[u]; v; v = bro[v])
if(ch[v] == s[i]) { found = true; break; }
if(!found)
{
v = sz++;
son[v] = ;
bro[v] = son[u];
son[u] = v;
tot[v] = ;
ch[v] = s[i];
}
ans += (tot[u] - - tot[v]) * ( * i + );
if(i == n) ans += tot[v] * ( * i + );
u = v;
tot[u]++;
}
}
}tire; const int maxl = + ;
char s[maxl]; int main()
{
//freopen("in.txt", "r", stdin); int n, kase = ;
while(scanf("%d", &n) == && n)
{
tire.clear();
ans = ;
for(int i = ; i < n; i++) { scanf("%s", s); tire.insert(s); }
printf("Case %d: %lld\n", ++kase, ans);
} return ;
}
代码君