題目鏈接：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、遞歸找下一個結點。

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxnode = 4000 * 1000 + 10; 6 const int sigma_size = 26; 7 8 struct Trie 9 { 10 int head[maxnode]; 11 int next[maxnode]; 12 char ch[maxnode]; 13 int tot[maxnode]; 14 int sz; 15 long long ans; 16 void clear() 17 { 18 sz = 1; 19 tot[0] = head[0] = next[0] = 0; 20 } 21 22 void insert(const char *s) 23 { 24 int u = 0, v, n = strlen(s); 25 tot[0]++; 26 for(int i = 0; i <= n; i++) 27 { 28 // 找字符a[i] 29 bool found = false; 30 for(v = head[u]; v != 0; v = next[v]) 31 if(ch[v] == s[i]) // 找到了 32 { 33 found = true; 34 break; 35 } 36 if(!found) 37 { 38 v = sz++; // 新建結點 39 tot[v] = 0; 40 ch[v] = s[i]; 41 next[v] = head[u]; 42 head[u] = v; // 插入到鏈表的首部 43 head[v] = 0; 44 } 45 u = v; 46 tot[u]++; 47 } 48 } 49 50 51 void dfs(int depth,int u) 52 { 53 if(head[u]==0) //葉子節點 54 ans+=tot[u]*(tot[u]-1)*depth; 55 else 56 { 57 int sum =0; 58 for(int v=head[u]; v!=0; v=next[v]) 59 { 60 sum+=tot[v]*(tot[u]-tot[v]); 61 } 62 ans+=sum/2*(2*depth+1); 63 for(int v=head[u]; v!=0; v=next[v]) 64 dfs(depth+1,v); 65 } 66 } 67 68 long long count() 69 { 70 ans = 0; 71 dfs(0,0); 72 return ans; 73 } 74 75 } trie; 76 77 char word[1010]; 78 79 int main() 80 { 81 int n; 82 int kase = 1; 83 while(scanf("%d",&n),n) 84 { 85 trie.clear(); 86 for(int i=0; i<n; i++) 87 { 88 scanf("%s",word); 89 trie.insert(word); 90 } 91 printf("Case %d: %lld\n",kase++,trie.count()); 92 } 93 94 return 0; 95 } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/6691301.html

總結

以上是生活随笔為你收集整理的Uva 11732 strcmp()函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。