SSOJ1437字符序列
4898+
作者：crxis 发布：2017-07-29 分类：深度优先搜索
题目大意：3个字母a、b、c，连成一个长度为n的字符串，要求任意相邻的2个子序列都不相同，共有多少种方案？
题目描述
从三个元素的集合[A，B，C]中选取元素生成一个N个字符组成的序列,使得没有两个相邻字的子序列相同。例：N = 5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子序列BC，AB是相同的。
输入
输入仅有一个整数n(1<=n<=15)。
输出
输出满足条件的N个字符的序列总数。
样例输入
4
样例输出
18
解题思路
n个格子，一个一个字符尝试填进去，如果不能填（出现相邻重复），则进行可行性剪枝，尝试另一个，当n个格子填完以后，累加方案数。
问题1：如何判断任意相邻2个子序列不重复？
由于进行了可行性剪枝，搜索进去以后，当前得到的字符串一定是没有相邻子序列重复的；加入一个字符后，如果会出现相邻子序列重复，那么后面的子序列一定包含最后一个字符，因此，我们只需要枚举后缀，如果出现后缀与字符串删去后缀后的后缀相同，即相邻重复。（枚举到字符串长度的一半即可）
问题2：如何比较两个后缀是否相同？
第一种是暴力枚举，逐个字符比较；第二种是用字符串函数：当前字符串长度为y，枚举子串长度x，用strncpy比较n个字符是否相等（strncpy(s+y-x, s+y-x-x, x)）；还可以用位运算，将字符串转成一个四进制书，每一位可以填1(01)、2(10)、3(11)，如果要比较后2为，即比较s%(1<<4)和s/(1<<4)%(1<<4)。
程序实现
