UVA - 11732 strcmp() Anyone?

题意：题目给出了标准strcmp()函数的代码，给你n个单词（n  <= 4000, len <= 1000， 大小写字母+数字），问你这些单词两两调用strcmp()函数一共比较了多少次

思路：字符串S1，S2比较分两种情况：S1和S2有相同的前缀S，那么ans = len(S)*2+1;

S1和S2完全相同的话：ans = （len(S)+1） * 2，等于算上了‘\0’

然后按照Trie的构造方法：采用了左儿子右兄弟的方法，但是看到网上的都是提交错误，就先存着

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 4000000;

struct Trie{
    int left[MAXN];
    int right[MAXN];
    int val[MAXN];
    char ch[MAXN];
    int cnt;
    long long ans;
    void init(){
        ch[0] = 0;
        left[0] = right[0] = val[0] = 0;
        cnt = 1,ans = 0;
    }
    void insert(char *s){
        int len = strlen(s),u = 0,j;
        for (int i = 0; i <= len; i++){
            for (j = left[u]; j; j = right[j])
                if (ch[j] == s[i])
                    break;
            if (j == 0){
                j = cnt++;
                ch[j] = s[i],right[j] = left[u];
                left[j] = 0,left[u] = j,val[j] = 0;
            }
            ans += (val[u]-val[j])*(i<<1|1);
            if (i == len){
                ans += val[j] * ((i+1) << 1);
                val[j]++;
            }
            val[u]++,u = j;
        }
    }
}tree;
char str[2000];

int main(){
    int n,cas = 1;
    while (scanf("%d",&n) != EOF && n){
        tree.init();
        for (int i = 0; i < n; i++){
            scanf("%s",str);
            tree.insert(str);
        }
        printf("Case %d: %lld\n",cas++,tree.ans);
    }
    return 0;
}

原文：http://blog.csdn.net/u011345136/article/details/19573727