uva 11732 "strcmp()" Anyone? (trie+左儿子右兄弟表示法)

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=28438

题意：定义了一个strcmp()函数，如图：

然后给出n个字符串s（n<=4000,|s|<=1000），问字符串两两调用strcmp函数（总共调用函数n(n-1)/2次）需要执行多少次判断。比如"aaa"和”aaa“需要8次，”that“和"than"需要7次。

分析：可以发现，对于不同的两个字符串比较的次数=最长公共前缀的长度*2+1，对于相同的两个字符串比较的次数=(字符串长度+1)*2。很容易想到用trie，但是最多可能有4000*1000个节点,用普通的trie存的话可能内存不够，需要用左儿子-右兄弟表示法来建树。。。。然而UVA的内存给的很大我开的4000 000*80的int型数组都可以(试了一下10 000 000*80的好像不行),居然可以水过~这里给出两种代码。

普通trie代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 4e6+5;
const int kd = 80;
char s[10000];
struct trie
{
int son[maxn][kd],end[maxn],L,root,dend[maxn];//end表示覆盖,dend表示结尾
long long ans;
int newnode()
{
dend[L]=end[L]=0;
fill(son[L],son[L]+kd,-1);
return L++;
}
void Init()
{
L=ans=0;
root=newnode();
}
void Insert(char str[])
{
ans+=end[root];
end[root]++;
int now=root,index,i;
for(i=0;str[i];i++)
{
index=str[i]-'0';
if(son[now][index]==-1)
son[now][index]=newnode();
now=son[now][index];
ans+=(end[now]<<1);
end[now]++;
}
ans+=dend[now];
dend[now]++;
}
}T;
int main()
{
int N,ncase=1;
while(scanf("%d",&N),N)
{
T.Init();
while(N--)
{
scanf("%s",s);
T.Insert(s);
}
printf("Case %d: %lldn",ncase++,T.ans);
}
return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 4e6+6;
struct trie
{
int lson[maxn];//lson[i]表示第i个节点的第一个左孩子的位置
int rbro[maxn];//rbro[i]表示第i个节点的第一个右兄弟的位置
char ch[maxn];//ch[i]表示第i个节点的字符
int cover[maxn];
int end[maxn];
int cnt,root;//节点数目
long long ans;
inline int newnode(const int &fa,const char &c) //父亲节点的下标,及新节点的字符
{//产生新节点,头插法,将每次产生的新节点作为父亲节点的第一个孩子
rbro[cnt]=lson[fa];
lson[cnt]=-1;
ch[cnt]=c;
cover[cnt]=end[cnt]=0;
lson[fa]=cnt;
return cnt++;
}
void Init() //0为虚节点(根)
{
ans=0;
cnt=0;
root=0;
rbro[cnt]=lson[cnt]=-1;
end[cnt]=cover[cnt]=ch[cnt]=0;
cnt++;
}
void Insert(char str[])
{
ans+=cover[root];
cover[root]++;
int now=root,i,j;
for(i=0;str[i];i++)
{
for(j=lson[now];~j;j=rbro[j])
if(str[i]==ch[j])
break;
if(j==-1) //没找到
j=newnode(now,str[i]);
now=j;
ans+=(cover[now]<<1);
++cover[now];
}
ans+=end[now];
++end[now];
}
}T;
char s[100000];
int main()
{
int N,ncase=1;
while(scanf("%d",&N),N)
{
T.Init();
while(N--)
{
scanf("%s",s);
T.Insert(s);
}
printf("Case %d: %lldn",ncase++,T.ans);
}
return 0;
} 

最后

以上就是心灵美荷花为你收集整理的uva 11732 "strcmp()" Anyone? (trie+左儿子右兄弟表示法)的全部内容，希望文章能够帮你解决uva 11732 "strcmp()" Anyone? (trie+左儿子右兄弟表示法)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。