UVa129 Krypton Factor（困难的串）

1、题目

2、题意

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

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

3、分析

基本框架不难确定：从左到右依次考虑每个位置上的字符。因此，问题的关键在于如何判断当前字符串是否已经存在连续的重复子串。例如，如何判断ABACABA是否包含连续重复子串呢？一种方法是检查所有长度为偶数的子串，分别判断每个字串的前一半是否等于后一半。尽管是正确的，但这个方法做了很多无用功。还记得八皇后问题中是怎么判断合法性的吗？判断当前皇后是否和前面的皇后冲突，但并不判断以前的皇后是否相互冲突——那些皇后在以前已经判断过了。同样的道理，我们只需要判断当前串的后缀，而非所有子串。

提示：在回溯法中，应注意避免不必要的判断，就像在八皇后问题中那样，只需判断新皇后和之前的皇后是否冲突，而不必判断以前的皇后是否相互冲突。

程序如下：

int dfs(int cur) { //返回0表示已经得到解，无须继续搜索
	if(cnt++ == n) {
		for(int i = 0; i < cur; i++) printf("%c", 'A' + S[i]); //输出方案
		printf("\n");
		return 0;
	}

	for(int i = 0; i < L; i++) {
		S[cur] = i;
		int ok = 1;
		for(int j = 1; j * 2 <= cur + 1; j++) { //尝试长度为j*2的后缀
			int equal = 1;
			
			for(int k = 0; k < j; k++) //检查后一半是否等于前一半
				if(S[cur - k] != S[cur - k - j]) { equal = 0; break; }
				
			if(equal) { ok = 0; break; } //后一半等于前一半，方案不合法
		}
		
		if(ok) 
			if(!dfs(cur + 1)) 
				return 0; //递归搜索。如果已经找到解，则直接退出
	}
	
	return 1;
}
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

有意思的是，$L=2$ 时一共只有 6 个串；当 $L\ge 3$ 时就很少回溯了。事实上，当 $L=3$ 时，可以构造出无限长的串，不存在相邻重复子串。

4、代码实现

#include
int n, L, cnt;
int S[100];

int dfs(int cur) { // 返回0表示已经得到解，无须继续搜索
	if(cnt++ == n) {
    	for(int i = 0; i < cur; i++) {
      		if(i % 64 == 0 && i > 0) printf("\n");
      		else if(i % 4 == 0 && i > 0) printf(" ");
      		printf("%c", 'A' + S[i]); // 输出方案
    	}
    	printf("\n%d\n", cur);
    	return 0;
  	}
  	
  	for(int i = 0; i < L; i++) {
    	S[cur] = i;
    	int ok = 1;
    	for(int j = 1; j * 2 <= cur + 1; j++) {// 尝试长度为j*2的后缀
      		int equal = 1;
      		for(int k = 0; k < j; k++) // 检查后一半是否等于前一半
        		if(S[cur - k] != S[cur - k - j]) { equal = 0; break; }		
      		if(equal) { ok = 0; break; } // 后一半等于前一半，方案不合法
    	}
    	
    	if(ok) 
    		if(!dfs(cur+1)) 
    			return 0;  // 递归搜索。如果已经找到解，则直接退出
  	}
  	return 1;
}

int main() {
	while(scanf("%d%d", &n, &L) == 2 && n > 0) {
    	cnt = 0;
    	dfs(0);
  	}
  	return 0;
}
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