有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 ;
}

最新文章

  1. [No000042]CSS 之 平时那些你不敢用的字体
  2. 使用Vs2012开发Metro时在另一台win8平板上调试的步骤
  3. AdaBoost算法实现
  4. MUI - DIV窗体切换
  5. APU平台DirectX 12性能测试:超级大惊喜!
  6. AFHTTPClient的异步回调模式
  7. 把多个JavaScript函数绑定到onload事件处理函数上
  8. 关于javascript 里面类型的判断
  9. PHOTOSHOP 半透明方格
  10. API HOOK库
  11. redux-form的学习笔记
  12. 蚂蚁金服新一代数据可视化引擎 G2
  13. JAVA字符串的常见处理和操作
  14. C语言函数指针与 c#委托和事件对比
  15. JavaScript数据类型之文本类型
  16. HDFS集群优化篇
  17. 理解交叉熵(cross_entropy)作为损失函数在神经网络中的作用
  18. java调用ws服务
  19. 使用 IntraWeb (5) - 页面布局之 TFrame
  20. [转]为什么Java中的HashMap默认加载因子是0.75

热门文章

  1. linux安装nagios客户端
  2. hadoop程序MapReduce之average
  3. linux系统socket通信编程2
  4. HTML5 ShadowDOM &amp; CustomElements
  5. 百度地图地址查询API使用
  6. 原创Java多线程详解(一)
  7. ubuntu android studio kvm
  8. 学习POC框架pocsuite--编写hellowordPOC
  9. collision weaknesses
  10. Squirrel语言初探(可以使用VC6或者MinGW编译)