uva11732 Trie转化
2024-08-22 09:27:53
有40001 个单词每个单词长度不超过1000,每个两个单词之间都要比较求要比较次数
int strcmp(char *s,char *t){
int i;
for(i = 0; s[i]==t[i]; ++i)
if(s[i]=='\0')
return 0;
return s[i]-t[i];
}
如果我们按照这样的去比较会超时,采用字典树,用孩子兄弟法求
#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = *+;
struct Trie{
int head[maxn];
int next[maxn];
char ch[maxn];
int tot[maxn];
int sz;
long long ans;
void clear(){
sz=;
head[]=next[]=tot[]=;
}
int idx(char c){ return c-'a';}
void insert(char *s){
int n= strlen(s);
int u=,v;
tot[]++;
for(int i=; i<=n; ++i){ bool found = false;
for( v = head[u]; v; v=next[v])
if(ch[v]==s[i]){ found=true; break; }
if(found==false){
v= sz++;
tot[v]=;
head[v]=;
next[v]=head[u];
head[u]=v;
ch[v]=s[i];
}
u=v;
++tot[u];
}
}
void dfs(int u,int len){
if(head[u]==){
ans+=tot[u]*(tot[u]-)*len;
}else{
int sum=;
for(int v= head[u]; v; v=next[v])
sum+=tot[v]*(tot[u]-tot[v]);
ans+= sum/*(*len+);
for(int v= head[u]; v; v=next[v])
dfs(v,len+);
} }
long long cut(){
ans=;
dfs(,);
return ans;
} }A;
char str[];
int main()
{
int n;
int cas=;
while(scanf("%d",&n)==&&n){
A.clear();
for(int i=; i<n; ++i){
scanf("%s",str);
A.insert(str);
}
printf("Case %d: %lld\n",cas++,A.cut());
}
return ;
}
最新文章
- [No000042]CSS 之 平时那些你不敢用的字体
- 使用Vs2012开发Metro时在另一台win8平板上调试的步骤
- AdaBoost算法实现
- MUI - DIV窗体切换
- APU平台DirectX 12性能测试:超级大惊喜!
- AFHTTPClient的异步回调模式
- 把多个JavaScript函数绑定到onload事件处理函数上
- 关于javascript 里面类型的判断
- PHOTOSHOP 半透明方格
- API HOOK库
- redux-form的学习笔记
- 蚂蚁金服新一代数据可视化引擎 G2
- JAVA字符串的常见处理和操作
- C语言函数指针与 c#委托和事件对比
- JavaScript数据类型之文本类型
- HDFS集群优化篇
- 理解交叉熵(cross_entropy)作为损失函数在神经网络中的作用
- java调用ws服务
- 使用 IntraWeb (5) - 页面布局之 TFrame
- [转]为什么Java中的HashMap默认加载因子是0.75