GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

判断第n个不包含连续子串的序列。

首先我们按照字典序生成序列，然后判断序列是否包含连续子串。

如果是包含连续子串的序列，那么这个序列后面无论再加多少个字符，都是包含连续子串的，因此不需要再递归了。

所以，对于当前我们要判断的长度为n的串，它的第1到n-1的串中肯定是没有包含连续子串的，此时加了第n个字符，那么我们就只需要判断包含最后这个字符的子串有没有发生重复的情况即可。

#include<stdio.h>int n, l, cur;
int arr[100];
bool flag; void print(int i) {for(int j = 1; j <= i; ++j) {printf("%c", 'A' + arr[j]);if(j%4 == 0 && j != i && j != 64) putchar(' ');if(j == 64 && j != i) putchar('\n');}printf("\n%d\n", i);
}bool judge(int i) {int j, k;for(j = 1; j <= i/2; ++j) {for(k = 0; k < j; ++k) {if(arr[i - k] != arr[i - k - j]) break;}if(k == j) return false;}return true;
}void dfs(int i) {if(i > 0 && !judge(i)) {return;}++cur;if(cur == n) {print(i);flag = true;return;}for(int j = 0; j < l; ++j) {arr[i+1] = j;dfs(i + 1); if(flag) return;}
}int main() {while(scanf("%d %d", &n, &l) == 2 && n) {cur = -1; flag = false;dfs(0);}return 0;
}