strcmp() Anyone?
uva11732:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2832&mosmsg=Submission+received+with+ID+13889354
题意：给你n个串，串之间两两进行比较，计算字符被比较的总次数。
题解：这里注意，' '也会被比较。这一题，看的是刘汝佳的代码，才知道怎么统计比较的次数。下面的代码，是刘汝佳的代码。
1 #include<cstring> 2 #include<vector> 3 using namespace std; 4 const int maxnode = 4000 * 1000 + 10; 5 const int sigma_size = 26; 6 // 字母表为全体小写字母的Trie 7 struct Trie { 8 int head[maxnode]; // head[i]为第i个结点的左儿子编号 9 int next[maxnode]; // next[i]为第i个结点的右兄弟编号 10 char ch[maxnode]; // ch[i]为第i个结点上的字符 11 int tot[maxnode]; // tot[i]为第i个结点为根的子树包含的叶结点总数 12 int sz; // 结点总数 13 long long ans; // 答案 14 void clear() { 15 sz = 1; 16 tot[0] = head[0] = next[0] = 0; 17 } // 初始时只有一个根结点 18 19 // 插入字符串s（包括最后的' '），沿途更新tot 20 void insert(const char *s) { 21 int u = 0, v, n = strlen(s); 22 tot[0]++; 23 for(int i = 0; i <= n; i++) { 24 // 找字符a[i] 25 bool found = false; 26 for(v = head[u]; v != 0; v = next[v]) 27 if(ch[v] == s[i]) { // 找到了 28 found = true; 29 break; 30 } 31 if(!found) { 32 v = sz++; // 新建结点 33 tot[v] = 0; 34 ch[v] = s[i]; 35 next[v] = head[u]; 36 head[u] = v; // 插入到链表的首部 37 head[v] = 0; 38 } 39 u = v; 40 tot[u]++; 41 } 42 } 43 44 // 统计LCP=u的所有单词两两的比较次数之和 45 void dfs(int depth, int u) { 46 if(head[u] == 0) // 叶结点 47 ans += tot[u] * (tot[u] - 1) * depth; 48 else { 49 int sum = 0; 50 for(int v = head[u]; v != 0; v = next[v]) 51 sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其他子树中再选一个 52 ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次 53 for(int v = head[u]; v != 0; v = next[v]) 54 dfs(depth+1, v); 55 } 56 } 57 58 // 统计 59 long long count() { 60 ans = 0; 61 dfs(0, 0); 62 return ans; 63 } 64 }; 65 #include<cstdio> 66 const int maxl = 1000 + 10; // 每个单词最大长度 67 int n; 68 char word[maxl]; 69 Trie trie; 70 int main() { 71 int kase = 1; 72 while(scanf("%d", &n) == 1 && n) { 73 trie.clear(); 74 for(int i = 0; i < n; i++) { 75 scanf("%s", word); 76 trie.insert(word); 77 } 78 printf("Case %d: %lld ", kase++, trie.count()); 79 } 80 return 0; 81 }