首页 > ACM题库 > HDU-杭电 > hdu 2651 Spring festival couplets-字典树-[解题报告]C++
2014
02-12

hdu 2651 Spring festival couplets-字典树-[解题报告]C++

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;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/8545076


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。