UVA 11732 - strcmp() Anyone?(Trie)

UVA 11732 - strcmp() Anyone?

題目鏈接

題意：給定一些字符串，要求兩兩比較，需要比較的總次數（注意，如果一個字符相同，實際上要還要和'\0'比一次，相當比2次）

思路：建Trie樹，每次建樹過程中，後繼後繼結點就是相同結點需要比較兩次ans + val * 2，否則就是不同結點ans + val，建完樹就計算完了

代碼：

#include 
#include 

const int N = 1005;
const int MAXN = 4000005;

int n;
char str[N];
long long ans;

struct Node {
    char c;
    int val;
} node[MAXN];

int first[MAXN], next[MAXN], sz;

void init() {
    ans = 0;
    sz = 1;
    first[0] = 0; next[0] = 0; node[0].val = 0;
}

void insert(char *str) {
    int u = 0, len = strlen(str);
    for (int i = 0; i <= len; i++) {
	bool flag = true;
	int v, tmp;
	for (v = first[u]; v; v = next[v]) {
	    if (node[v].c == str[i]) {
		tmp = v;
		flag = false;
		ans += node[v].val * 2;
	    }
	    else ans += node[v].val;
	}
	if (flag) {
	    v = sz++;
	    node[v].c = str[i];
	    node[v].val = 0;
	    first[v] = 0;
	    next[v] = first[u];
	    first[u] = v;
	}
	else v = tmp;
	u = v;
	node[u].val++;
    }
}

int main() {
    int cas = 0;
    while (~scanf("%d", &n) && n) {
	init();
	while (n--) {
	    scanf("%s", str);
	    insert(str);
	}
	printf("Case %d: %lld\n", ++cas, ans);
    }
    return 0;
}