Trie 字典树（附数据生成程序）
题意非常好懂。就问一堆单词两两比較要多少次。
只是非常忧伤的是卡优化了。写了个数据生成，然后我跟别人程序比。用时大概是别人的一倍。
别人635ms 过了。我就TLE…… 问题是2000ms啊。
给跪了。
附数据生成程序，各位能够生成数据看看。愿不要TLE。
我的TLE了……：
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int n,m;
LL ans;
struct Trie
{
int word[4001*1001][26*2+11];
int sz,cot;
int ex[4001*1001];
int fin[4001*1001];
void intTrie()
{
sz=1;
cot=1;
memset(word[0],0,sizeof(word[0]));
ex[0]=0;
fin[0]=0;
}
int shift(char s)
{
int c=0;
if(s>='a'&&s<='z')
c=s-'a';
else if(s>='A'&&s<='Z')
c=s-'A'+26;
else if(s>='0'&&s<='9')
c=s-'0'+52;
return c;
}
int insert(char *s)
{
int u=0,c;
ans+=ex[0];
ex[0]++;
for(int i=0; s[i]!=' '; i++)
{
c=shift(s[i]);
if(!word[u][c])
{
memset(word[sz],0,sizeof(word[sz]));
ex[sz]=0;
fin[sz]=0;
word[u][c]=sz++;
}
u=word[u][c];
ans+=ex[u]*2;
ex[u]++;
}
ans+=fin[u];
fin[u]++;
}
}wo;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("1.txt","w",stdout);
char str[1011];
int nn=1;
while(scanf("%d",&n),n)
{
wo.intTrie();
ans=0;
for(int i=0; i<n; i++)
{
scanf("%s",str);
wo.insert(str);
}
printf("Case %d: %lld
",nn++,ans);
}
return 0;
}
数据生成：
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#include<ctime>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
time_t t;
void build()
{
t++;
srand(t);
int n=rand()%1000;
printf("%d
",n);
while(n--)
{
t++;
srand(t);
int len=rand()%1000+1;
for(int i=0;i<len;i++)
{
t++;
srand(t);
int c=rand()%26;
int flag=rand()%3;
if(flag==0)
printf("%c",c+'a');
else if(flag==1)
printf("%c",c+'A');
else
{
c%=10;
printf("%c",c+'0');
}
}
printf("
");
}
}
int main()
{
freopen("in.txt","w",stdout);
time(&t);
srand(t);
//int m=rand()%100;
int m=300;
while(m--)
{
build();
}
printf("0
");
return 0;
}