一、 题意分析
定义：称一个满足劳拉设想的序列为一个重复序列。那么题目要求判断一个序列是否是一个重复序列。
生成重复序列的方法是将原序列复制一遍，然后按顺序插入到原序列中对应字符之后间隔若干个字符（指原序列中的字符）的位置上，要求是在生成的重复序列中，两个对应字符之间间隔的其它字符不能超过9个。
二、 算法分析
由于问题中给定的重复序列可能很长，产生的状态数为 级（设给出的序列长度为n），因此无法用有效的算法（复杂度为多项式级的算法）来解决，只有采用搜索算法。
搜索方法
依次处理每一位字符，考虑两种情况：这个字符属于原序列或者属于被复制的序列。这样算法的时间上限是。
优化
考虑到问题中的状态数很大，因此，需要对搜索算法进行优化。以下给出三种可行有效的优化方法。
1、 排除一部分无解的情况。
对一些可以事先判断出不是重复序列的情况，可以不进行搜索，以提高程序效率。这里只考虑几种显而易见的无解情况。
首先，如果在给出的字符序列中一种字符出现了奇数次，则一定无解；其次，当每一种字符都出现偶数次的时候，如果第I*2－1次出现和第I*2次出现的位置中间间隔了超过9各字符（I>0），则肯定无解。
2、 剪枝，排除搜索中无用的分支。
如果当前的字符属于被复制的序列，那么它一定与被复制序列中最后一个未被匹配的字符相等，只有这样才可以搜索这个字符属于被复制序列的情况。
如果当前的字符属于原序列，那么原序列中未被匹配的字符数不能超过10个（包含当前字符），否则就不满足劳拉的假设。
此外，因为最终原序列和被复制序列相同，那么它们的长度一定相同，则如果当前的选择必定造成两个序列长度不同，也可以剪枝。
3、 判重，尽可能减少重复的工作。
经过以上两步的优化，算法已经可以适应大部分的数据，但还有一些特殊的情况会超时。通过对这些特殊情况的分析，可以发现一个算法的致命缺点：无法避免大量的重复状态。应为题目中的状态总数最多可以达到，因此采用一般的办法要么空间无法承受；要么需要花费太大的时间代价，反而得不偿失。
状态表示
通过分析，可以发现所有重复的状态的一个特征：在同一时刻，如果两个状态未被匹配的部分相同，那么这两个状态一定是重复的，可以不必继续搜索。因此，我们可以以每个状态所处的时刻和未被匹配的部分作为它的特征。
判重方法
由于状态数太多，且之间没有规律，因此可以考虑用HASH表判重，这样可以尽快地排除重复的状态。
因为状态数太多，无法全部存下，因此如果HASH表已满，则不再将新的状态存入表中。也就是说HASH表不能在装下当前状态时，就只判重，而不将为出现过的状态存下。
尽管第三种优化方法具有一定的极限性，但他可以排除大量重复的计算，还是相当有效的。
说明：通过以上三步优化，程序可以在很短的时间内通过所有的测试数据。当然，这只是针对一些特殊的情况所作的优化，对于一些特定的数据仍然无法满足时间上的要求。（因为无论怎样优化，都不能改变算法时间复杂度是指数级这个事实）
|
