紫书例题7-5 困难的串

Posted on | In |

如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。例如， BB、ABCDABCD都是容易的串，而D、DC、ABDAD、CBABCBA都是困难的串。

输入正整数n和L，输出由前L个字符组成的、字典序第k个困难的串。例如，当L=3时，前7个困难的串 分别为A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。输入保证答案不超过80个字符。

样例输入：

7  3

30 3

样例输出：

ABACABA

ABACABCACBABCABACABCACBACABA

1
2
3
4
5
6
在回溯算法中，应注意避免不必要的判断，八皇后问题中，只需判断新皇后和之前的皇后是否冲突，而不必判断以前的皇后是否相互冲突。 
这一题只需判断当前串的偶数项后缀是否对称

BB,长度为1*2的后缀对称 
ABCDACABCAB,长度为3*2的后缀对称 
ABCDABCD长度为4*2的后缀对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;
int	s[100];
int	n;
int	L;
int  dfs( int cur )
{
	if ( cur == n )
	{
		for ( int i = 0; i < n; i++ )
			printf( "%c", 'A' + s[i] );
		printf( "\n" );
		return(0);
	}else  {
		for ( int i = 0; i < L; i++ )
		{
			s[cur] = i;
			int ok = 1;
			for ( int j = 1; 2 * j <= cur + 1; j++ )        /* 尝试j*2的后缀 */
			{ /* 如j=1 尝试1*2的后缀 看看是否重复 */
				int equal = 1;                          /* !!! */
				for ( int k = 0; k < j; k++ )
				{
					if ( s[cur - k] != s[cur - j - k] )
              //只要确定了后缀j*2中有一个不相等，则可以确定前一半与后一半不相等
					{
						equal = 0;
						break;
					}
				}
				if ( equal == 1 )
				{
					ok = 0;
				}
			}
			if ( ok == 1 )
			{
				if ( !dfs( cur + 1 ) )
					return(0);  //!! 最后一层算完 会返回上一层 如果已经找到解就退出 
			}
		}
	}
}


int main()
{
	cin >> n >> L;
	dfs( 0 );


	return(0);
}