首页 > 代码库 > uva11732 Trie转化
uva11732 Trie转化
有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 = 4001*1000+10;struct Trie{ int head[maxn]; int next[maxn]; char ch[maxn]; int tot[maxn]; int sz; long long ans; void clear(){ sz=1; head[0]=next[0]=tot[0]=0; } int idx(char c){ return c-‘a‘;} void insert(char *s){ int n= strlen(s); int u=0,v; tot[0]++; for(int i=0; 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]=0; head[v]=0; next[v]=head[u]; head[u]=v; ch[v]=s[i]; } u=v; ++tot[u]; } } void dfs(int u,int len){ if(head[u]==0){ ans+=tot[u]*(tot[u]-1)*len; }else{ int sum=0; for(int v= head[u]; v; v=next[v]) sum+=tot[v]*(tot[u]-tot[v]); ans+= sum/2*(2*len+1); for(int v= head[u]; v; v=next[v]) dfs(v,len+1); } } long long cut(){ ans=0; dfs(0,0); return ans; }}A;char str[1002];int main(){ int n; int cas=1; while(scanf("%d",&n)==1&&n){ A.clear(); for(int i=0; i<n; ++i){ scanf("%s",str); A.insert(str); } printf("Case %d: %lld\n",cas++,A.cut()); } return 0;}
uva11732 Trie转化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。