【uva11732】strcmp() Anyone?

本文主要是介绍【uva11732】strcmp() Anyone?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/UVA-11732
题解：
建一棵trie树，每次经过一个点，该点的计数器+1
插入的时候顺便统计，分字符相同（*2）和不同（*1）讨论一下就好
注意最后一位的比较，可以都赋值为47（’\’）
考虑到串只有4000个但串比较长，需要使用左儿子右兄弟表示法

下面的代码会T，我也没办法啊（一脸无辜），路过的大佬们帮忙看看
时限2s，极限数据3.5s，难道这就是所谓的卡常数？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;const int N=4000010;
int son[N],bro[N],val[N];
int T,n;
LL ans;
char str[4010];
char ch[N];
int size;void insert(char *s)
{int len=strlen(s+1),t=1,p;val[1]++;for(int i=1;i<=len+1;i++){for(p=son[t];p;p=bro[p])if(ch[p]==s[i]) break;if(p==0) {p=++size;ch[p]=s[i];bro[p]=son[t];son[p]=0;val[p]=1;son[t]=p;ans+=val[t]-1;t=p;}else ans+=val[t]-1+val[t],val[p++],t=p;}
}int main()
{
//  freopen("in.in","r",stdin);
//  freopen("out1.out","w",stdout);while(~scanf("%d",&n)&&n){size=1;ch[1]=val[1]=bro[1]=son[1]=0;ans=0;for(int i=1;i<=n;i++){scanf("%s",str+1);insert(str);}printf("Case %d: %lld\n", ++T, ans);}return 0;
}

这篇关于【uva11732】strcmp() Anyone?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---