题意:给出多个字符串,两两配对,求总配对次数。
思路:如果两个字符串一样,ans=strlen(字符串)*2+2,如果不同,ans=公共前缀长度*2+1;用左儿子右兄弟建字典树。插入一个字符计算一次。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn=;
const int maxnode=;
typedef long long LL; struct trie
{
int son[maxnode];
int bro[maxnode];
char ch[maxnode];
LL ans;
int num[maxnode];
int sizee; void init()
{
sizee=;
son[]=bro[]=num[]=;
ans=;
} void insertt(char *s)
{
int len=strlen(s);
int p,u=;
for(int i=; i<=len; i++)
{
for(p=son[u]; p; p=bro[p])
{
if(ch[p]==s[i])
break;
}
if(!p)
{
p=sizee++;
ch[p]=s[i];
bro[p]=son[u];
son[p]=;
num[p]=;
son[u]=p;//p为u的左儿子
}
ans+=(num[u]-num[p])*(*i+);//前缀长度为i,当前这个字母的比较次数为num[u]-num[p]
if(i==len)//匹配到最后一个字符,还需与当前这个字母相同的字符比较,而且之前减去num[p]次
{
ans+=num[p]*(*i+);
num[p]++;
}
num[u]++;
u=p;
}
}
} T; int main()
{
int n,cas=;
char str[];
while(~scanf("%d",&n)&&n)
{
T.init();
for(int i=; i<n; i++)
{
scanf("%s",str);
T.insertt(str);
}
printf("Case %d: %lld\n",cas++,T.ans);
}
return ;
}