本文主要是介绍UVA - 11732 （前缀树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目网址点击打开链接
；
这个题题意是这样的：就是给你字符串进行两两比对，看需要比多少次==，注意相等时==结果ans+=2，如果此位不相等 ans+=1，并且结束比较
注意！！！所有的串的比较结束时要么两个不相等，要么至少一个到\0；但是
wa点来（wsb）
例 wsb wsb比较答案应该是8，而不是6 还需要比较最后一位的\0；
竟无语凝噎，因为这，我死磕了一下午加一晚上，就是不想跟着题解走，认为自己没错，竟然忘了uva有debug这个东西，可以帮忙，最后发现样例跟自己手算的答案都不一样，突然顿悟可能是我傻逼的又把题目搞错了
上代码：
两种代码，一种直接建树（小心一点内存够用，还不会TE），一种通过左儿子右兄弟建树
至于如何计数，加上\0之后，情况简单了很多，直接推一推，求一求自己画图一看就能推出来
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<string>
#include<set>
#include<cmath>
#include<vector>using namespace std;
const int maxmode=4000000+5;
const int maxn=40000+5;
long long ans;
struct node
{int ch[maxmode][80];int sz;int cd;int val[maxmode];node(){sz=1;cd=0;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));}void build(){sz=1;cd=0;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));}int init(string a,int ff){long long res=0;int flag=0;int u=0;int n=a.size();for(int i=0;i<n+1;i++){int c;if(i==n)c=0;else if(a[i]<='9'&&a[i]>='0')c=a[i]-'0'+1;else if(a[i]>='a'&&a[i]<='z')c=a[i]-'a'+12;else if(a[i]>='A'&&a[i]<='Z')c=a[i]-'A'+40;if(!ch[u][c]){flag=1;res+=val[u];ch[u][c]=sz++;val[sz]=0;}else{res+=val[u];res+=(val[ch[u][c]]);}val[u]++;u=ch[u][c];}val[u]++;return res;}
};
node s;
int main()
{int ka=0;int n;while(cin>>n&&n){ka++;s.build();string a;ans=0;for(int i=0;i<n;i++){cin>>a;ans+=s.init(a,i);}printf("Case %d: ",ka);cout<<ans<<endl;}return 0;
}
左右儿子
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<string>
#include<set>
#include<cmath>
#include<vector>using namespace std;
const int maxmode=4000000+5;
const int maxn=1000+5;
long long ans;
struct node
{int son[maxmode];int bro[maxmode];int tot[maxmode];char ch[maxmode];int sz;node(){sz=1;son[0]=bro[0]=tot[0]=0;}void build(){sz=1;son[0]=bro[0]=tot[0]=0;}int init(string a,int ff){long long res=0;int u=0,v;int n=a.size();for(int i=0;i<n;i++){int flag=0;for(v=son[u];v;v=bro[v]){if(ch[v]==a[i]){flag=1;break;}}if(!flag){v=sz++;res+=tot[u];ch[v]=a[i];son[v]=0;bro[v]=son[u];son[u]=v;tot[v]=0;}else{res+=tot[u];res+=(tot[v]);}tot[u]++;u=v;}tot[u]++;//cout<<res<<endl;return res;}
};
node s;
int main()
{int ka=0;int n;string aa;//freopen("out.txt","w",stdout);//cout<<a<<endl;while(cin>>n&&n){ka++;s.build();string a;ans=0;for(int i=0;i<n;i++){cin>>a;a+=".";ans+=s.init(a,i);}printf("Case %d: ",ka);cout<<ans<<endl;}return 0;
}
如果\0记录一下错误理解题意
else{// cout<<"kjdfhsdjkfhjkerhg"<<endl;if(c!=0)res+=val[u];if(c!=0)res+=(val[ch[u][c]]);elseres+=val[u]-val[ch[u][c]];//if(ff==5&&c==0)// cout<<val[ch[u][c]]<<endl;//cout<<res<<endl;}
这篇关于UVA - 11732 （前缀树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
