首页 > 代码库 > 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;}
View Code

 

uva11732 Trie转化