Uva 11732 strcmp()函数

题目链接：https://vjudge.net/contest/158125#problem/A

题意：

系统中，strcmp函数是这样执行的，给定 n 个字符串，求两两比较时，strcmp函数要比较多少次？

如：

t h a n \n t h e r e \n

t h a t \n t h e \n

2 2 2 1 2 2 2 1

直接两两比较是超时的。

可以这样建立一个字典树：

可以发现一直要比较到交叉处，和这个交叉点的深度有关(2*depth+1)。

1、这个字典序每一个交叉点都是要计算的，所以采用邻接表的形式存图；

2、每个结点都要计算他的叶子结点的个数，当分叉的时候，那么说明这里有两个（多个）不同的单词，从中要选择两个单词，计算有多少种搭配，比较次数就是这些搭配*(2*depth+1);

3、递归找下一个结点。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxnode =  *  + ;

 const int sigma_size = ;

 struct Trie

 {

     int head[maxnode];

     int next[maxnode];

     char ch[maxnode];

     int tot[maxnode];

     int sz;

     long long ans;

     void clear()

     {

         sz = ;

         tot[] = head[] = next[] = ;

     }

     void insert(const char *s)

     {

         int u = , v, n = strlen(s);

         tot[]++;

         for(int i = ; i <= n; i++)

         {

             // 找字符a[i]

             bool found = false;

             for(v = head[u]; v != ; v = next[v])

                 if(ch[v] == s[i])   // 找到了

                 {

                     found = true;

                     break;

                 }

             if(!found)

             {

                 v = sz++; // 新建结点

                 tot[v] = ;

                 ch[v] = s[i];

                 next[v] = head[u];

                 head[u] = v; // 插入到链表的首部

                 head[v] = ;

             }

             u = v;

             tot[u]++;

         }

     }

     void dfs(int depth,int u)

     {

         if(head[u]==) //叶子节点

             ans+=tot[u]*(tot[u]-)*depth;

         else

         {

             int sum =;

             for(int v=head[u]; v!=; v=next[v])

             {

                 sum+=tot[v]*(tot[u]-tot[v]);

             }

             ans+=sum/*(*depth+);

             for(int v=head[u]; v!=; v=next[v])

                 dfs(depth+,v);

         }

     }

     long long count()

     {

         ans = ;

         dfs(,);

         return ans;

     }

 } trie;

 char word[];

 int main()

 {

     int n;

     int kase = ;

     while(scanf("%d",&n),n)

     {

         trie.clear();

         for(int i=; i<n; i++)

         {

             scanf("%s",word);

             trie.insert(word);

         }

         printf("Case %d: %lld\n",kase++,trie.count());

     }

     return ;

 }

巴特西

Uva 11732 strcmp()函数

最新文章

热门文章