记录编号	431945	评测结果	AAAAAAAAAA
题目名称	2695.strcmp()函数	最终得分	100
用户昵称	joel	是否通过	通过
代码语言	C++	运行时间	1.204 s
提交时间	2017-08-02 15:32:54	内存使用	7.77 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int M = 1000 + 10;
class Node
{
public:
	Node *LC,*RB;
	char c;
	int size;
	Node():LC(NULL),RB(NULL),c(' '),size(0){}
};
class Trie
{
public:
	Node* root;
	long long ans;
	Trie():root(NULL),ans(0){}
	
	void INS(const char *s)
	{
		int lens = strlen(s);
		Node *v,*p=root;
		p->size++;
		for(int i = 0;i <= lens;i++)
		{
			bool found = false;
			for(v = p->LC; v != NULL; v = v->RB)
				if(v->c == s[i])
				{
					found = true;
					break;
				}
			if(!found)
			{
				v = new Node;
				v->c = s[i];
				v->RB = p->LC;
				p->LC = v;
			}
			p = v;
			p->size++;
		}
	}
	
	void dfs(int depth,Node *p)
	{
		if(p->LC == NULL)
			ans += p->size * (p->size-1) * depth;
		else
		{
			int sum = 0;
			for(Node* i = p->LC; i != NULL; i = i->RB)
				sum += i->size * (p->size - i->size);
			ans += sum / 2 * (2 * depth + 1);
			for(Node* i = p->LC; i != NULL; i = i->RB)
				dfs(depth+1,i);
		}
	}
	
	long long Count()
	{
		ans = 0;
		dfs(0,root);
		return ans;
	}
};
char s[M];
Trie T;
int main()
{
	freopen("strcmp.in","r",stdin);
	freopen("strcmp.out","w",stdout);
	int kase = 1,n;
	while(scanf("%d",&n)&&n)
	{
		T.root = new Node;
		for(int i = 1; i <= n; i++)
		{
			scanf("%s",s);
			T.INS(s);
		}
		printf("Case %d: %lld\n", kase++, T.Count());
	}
	return 0;
}