题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2832
按照正常的字典树建树会MLE
所以需要采用树的压缩算法来建树
#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 4000010
#define maxl 1010
using namespace std; typedef long long LL; typedef struct _node {
char value;
int size;
int count;
_node* lchild;
_node* rchild;
} node; node dict[maxn];
char str[maxl]; class Trie
{
private:
LL count;
int size;
node* root; public: Trie()
{
init();
} void init()
{
memset( dict, , sizeof(dict));
size = ;
count = ;
root = new_node();
} node* new_node(char c)
{
dict[size].value = c;
return &dict[size++];
} void insert(char* word)
{
int len = (int)strlen(word), same = ;
node* now = root->rchild;
node* pa = root;
for (int i = ; i <= len; ++i)
{
if (!now)
{
pa->rchild = new_node( word[i]);
now = pa->rchild;
now->count = ;
same = ;
}
else
{
if (i)
count += now->count;
count += now->count++; while (now->lchild && now->value != word[i])
now = now->lchild;
if (now->value != word[i])
{
now->lchild = new_node( word[i]);
now = now->lchild;
same = ;
}
}
pa = now;
now = pa->rchild;
} if (same)
pa->size++;
count += pa->size;
} LL query()
{
return count;
}
} trie; int main(void)
{
int ca = , n;
while (scanf("%d", &n), n)
{
Trie trie = Trie();
for (int i = ; i < n; ++i)
{
scanf("%s", str);
trie.insert( str);
}
printf("Case %d: %lld\n", ca++, trie.query());
}
return ;
}