UVa 11732 "strcmp()" Anyone? （左儿子右兄弟前缀树Trie）

题意：给定strcmp函数，输入n个字符串，让你用给定的strcmp函数判断字符比较了多少次。

析：题意不理解的可以阅读原题https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2832

字符串很多，又很长，如果按照题目的意思两两比较，肯定会TLE，所以要用前缀树（Trie）来解决，当然只是用简单的前缀树也会TLE的，

我们必须对其进行优化，看了网上大牛们的，知道要用左儿子右兄弟的方法来优化，说实话，以前还没用过，看了好久才明白是什么个意思，

不是很明白的画个图想一想就会明白的，我采用的是边插入边计算的方法，在每一个分枝都进行计算，然后加和，我们要找每个分枝，

除了最后一个都是2*i+1，最后一个再加上2*i+2。

代码如下：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long LL;

const int maxn = 4000 * 1000 + 10;

LL ans = 0;

char s[1010];

struct Trie{

    int lson[maxn];

    int rbro[maxn];

    int val[maxn];

    char ch[maxn];

    int sz;

    void clear(){  sz = 1; lson[0] = rbro[0] = val[0] = 0;  ans = 0; }

    void insert(const char *s){

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

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

            for(v = lson[u]; v; v = rbro[v])

                if(s[i] == ch[v])  break;//找到结点

            if(!v){//新建结点

                v = sz++;

                ch[v] = s[i];

                lson[v] = 0;//左儿子为空

                rbro[v] = lson[u];//结点放在首部

                val[v] = 0;//初始化

                lson[u] = v;//插入结点

            }

            ans += (val[u]-val[v]) * (2 * i + 1);//(val[u]-val[v])意思是和v不一样的单词数

            if(i == n){

                ans += val[v] * (2 * i + 2);

                ++val[v];

            }

            ++val[u];  u = v;

        }

    }

};

Trie trie;

int main(){

    int n, kase = 0;

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

        trie.clear();

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

            scanf("%s", s);

            trie.insert(s);

        }

        printf("Case %d: %lld\n", ++kase, ans);

    }

    return 0;

}

下面是大牛Rujia Liu的代码，我基本是根据他的代码写的（因为自己确实是写不出来。。。）

// UVa11732 strcmp() Anyone?

// Rujia Liu

#include<cstring>

#include<vector>

using namespace std;

const int maxnode = 4000 * 1000 + 10;

const int sigma_size = 26;

// 字母表为全体小写字母的Trie

struct Trie {

  int head[maxnode]; // head[i]为第i个结点的左儿子编号

  int next[maxnode]; // next[i]为第i个结点的右兄弟编号

  char ch[maxnode];  // ch[i]为第i个结点上的字符

  int tot[maxnode];  // tot[i]为第i个结点为根的子树包含的叶结点总数

  int sz; // 结点总数

  long long ans; // 答案

  void clear() { sz = 1; tot[0] = head[0] = next[0] = 0; } // 初始时只有一个根结点

  // 插入字符串s（包括最后的'\0'），沿途更新tot

  void insert(const char *s) {

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

    tot[0]++;

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

      // 找字符a[i]

      bool found = false;

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

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

          found = true;

          break;

        }

      if(!found) {

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

        tot[v] = 0;

        ch[v] = s[i];

        next[v] = head[u];

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

        head[v] = 0;

      }

      u = v;

      tot[u]++;

    }

  }

  // 统计LCP=u的所有单词两两的比较次数之和

  void dfs(int depth, int u) {

    if(head[u] == 0) // 叶结点

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

    else {

      int sum = 0;

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

        sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其他子树中再选一个

      ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次

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

        dfs(depth+1, v);

    }

  }

  // 统计

  long long count() {

    ans = 0;

    dfs(0, 0);

    return ans;

  }

};

#include<cstdio>

const int maxl = 1000 + 10;   // 每个单词最大长度

int n;

char word[maxl];

Trie trie;

int main() {

  int kase = 1;

  while(scanf("%d", &n) == 1 && n) {

    trie.clear();

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

      scanf("%s", word);

      trie.insert(word);

    }

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

  }

  return 0;

}