2014
02-12

# Spring festival couplets

When the spring festival is coming , people always paste spring festival couplets onto the wall.Now dandelion’s father has bought several spring festival couplets, he wants to know how many pairs of spring festival couplets can been consisted with these spring festival couplets.As we know ,spring festival couplets are carefully balanced.Such as AABBCCDD can only be matched with AABBCCDD or BBDDEEFF or AABBAABB …

A number n stands for the number of the spring festival couplets.(2≤n≤110000)
Then n lines ,each line contains a string made by capital letters. Such as AABBCCDD,AABBCCD.The length of the string will not exceed 8.

A number n stands for the number of the spring festival couplets.(2≤n≤110000)
Then n lines ,each line contains a string made by capital letters. Such as AABBCCDD,AABBCCD.The length of the string will not exceed 8.

6
ABCCCDA
LLLMNNO
DEZZZBF
AAABCCD
KKKXPPQ
AAA

4

/*

水题，把每个读入的串，根据相邻字母重复次数，

我这个用了字典树，也可以不用，直接把所有构

2013-01-26
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int n;
__int64 ans;
struct Dictree
{
struct Dictree *child[9];
int num;
};
struct Dictree *root;

void insert(char str[])
{
struct Dictree *now,*next;
int i,l;
now=root;
for(i=0;str[i];i++)
{
if(now->child[str[i]-'0']!=NULL)
now=now->child[str[i]-'0'];
else
{
next=(struct Dictree *)malloc(sizeof(struct Dictree));
next->num=0;
for(l=1;l<=8;l++)	next->child[l]=NULL;
now->child[str[i]-'0']=next;
now=next;
}
}
now->num++;
}
void get_ans(struct Dictree *now)
{
int l;
__int64 temp=now->num-1;
ans+=(1+temp)*temp/2;
for(l=1;l<=8;l++)
if(now->child[l]!=NULL)
get_ans(now->child[l]);
}
int main()
{
int i,l;
int temp,k;
char str1[22],str2[22];
while(scanf("%d",&n)!=-1)
{
root=(struct Dictree *)malloc(sizeof(struct Dictree));
root->num=0;
for(l=1;l<=8;l++)	root->child[l]=NULL;
for(i=0;i<n;i++)
{
scanf("%s",str1);
k=0;
temp=1;
for(l=1;str1[l];l++)
{
if(str1[l]!=str1[l-1])
{
str2[k++]=temp+'0';
temp=1;
}
else	temp++;
}
str2[k++]=temp+'0';
str2[k]=0;
insert(str2);
}
ans=0;
get_ans(root);
printf("%I64d\n",ans);
}
return 0;
}