左儿子右兄弟Trie UVA 11732 strcmp() Anyone?

题目地址：

题意： 

问strcmp函数的==语句运行了几次。

分析： 

大白上的题目。 

听说要用左儿子右兄弟的Trie。比較省空间。顺便学了下。

一边insert一边统计。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define repf(i,a,b) for(int i=(a);i<=(b);i++)

typedef long long ll;

const int N = 0;

const int MAXNODE =	4000010;

int n, cas;

ll ans;

char str[4001];

struct STrie {

	int son[MAXNODE];

	int bro[MAXNODE];

	int val[MAXNODE];

	char ch[MAXNODE];

	int sz;

	STrie() { sz = 1; ch[0] = val[0] = bro[0] = son[0] = 0; }

	void init() { sz = 1; ch[0] = val[0] = bro[0] = son[0] = 0; }

	// inline int idx(char c) { return c - 'a'; }

	void insert(char *s) {

		int len = strlen(s), u = 0, p;

		repf (i, 0, len) {

			// check the brother of u

			for (p = son[u]; p; p = bro[p]) {

				if (ch[p] == s[i])

					break;

			}

			// cannot find out than insert

			if (!p) {

				p = sz++;

				ch[p] = s[i];

				bro[p] = son[u];

				son[p] = 0;

				val[p] = 0;

				son[u] = p;

			}

			ans += (val[u] - val[p]) * (2 * i + 1);

			if (len == i) {

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

				val[p]++;

			}

			val[u]++;

			u = p;

		}

	}

} trie;

int main() {

	// ios_base::sync_with_stdio(0);

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

		trie.init();

		ans = 0;

		repf (i, 0, n - 1) {

			scanf("%s", str);

			trie.insert(str);

		}

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

	}

	return 0;

}

// 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;

}