UVa 11732-strcmp() Anyone?

由于数据规模的原因，需要用多叉树来构建Trie，即一个结点的子树通过一个子节点串起来，这样节省很多空间。本代码的Node.count为插入时搜索路径经过该结点的次数，表明多少个字符串在Trie相应的深度位置和当前字符串里的相应位置的字符相等，如果相等就要加上其次数乘上2，如果不相等直接加上其次数。

#include <cstdio>
#include <memory.h>
#include <cstring>
#define maxnode 4000005
#define LL long long
using namespace std;
struct Node{
	char ch;
	Node* brother;
	Node* child;
	int count;
};
Node map[maxnode];
class Trie{
public:
	Node* root;
	LL ans;
	int sz;
	void Initial(){
		sz=1;
		ans=0;
		root=NewNode(0);
	}
	Node* NewNode(char c){
		map[sz].ch=c;
		map[sz].brother=map[sz].child=NULL;
		map[sz].count=0;
		return &map[sz++];
	}
	void Trie_Insert(char str[],int n){
		Node* node=root->child,*last=root;
		bool flag;
		for(int i=0;i<=n;++i){
			flag=0;
			for(Node* next=node;next!=NULL;next=next->brother){
				if(next->ch==str[i]){
					flag=1;
					node=next;
					ans+=next->count*2;
				}else	ans+=next->count;
			}
			if(!flag){
				Node* temp=NewNode(str[i]);
				temp->brother=last->child;
				last->child=temp;
				node=temp;
			}
			node->count++;
			last=node;
			node=node->child;
		}
	}
};
int main(){
	int n,len=1;
	char str[1010];
	Trie trie;
	while(~scanf("%d",&n)){
		if(n==0)	break;
		getchar();
		trie.Initial();
		while(n--){
			gets(str);
			trie.Trie_Insert(str,strlen(str));
		}
		printf("Case %d: %lld\n",len++,trie.ans);
	}
	return 0;
}