题意:
输入正整数n,l,输出由前l个字符组成的,字典序第k小的没有两个相邻重复子串的串。
要点:
判断ABCABA是否包含重复子串的方法是这样的:运用回溯法,只要比较当前串后缀,因为回溯法的特性,我们只要考虑当前的情况即可,前面的不用管,这样递归可以保证从头到尾都是成立的,当然后缀要从一个比较到n+1/2个(奇数多考虑一个),例如:ABCABA,先比较A与前面的B,再比较BA与CA,以此类推。
注意这里有一个非常难想到的地方:我们递推考虑的是往字符串上一个个加字母,但有时会出现加上去的字母都不满足的情况,如:ABACABA,不管加A,B,C都不行,这时候输出的应该是返回前一个的值ABACABC,所以多设一个值num储存字典序,cur储存个数。
代码如下:
#include<stdio.h>
#include<string.h>
int s[100];
int n, l,num;//用num存储字典序bool judge(int cur)
{int j, k;for (j = 1; j * 2 <= cur + 1; j++)//后缀长度从1判断到cur+1,+1是考虑到奇数情况{bool flag = true;for (k = 0; k < j; k++)if (s[cur - k] != s[cur - k - j])//前后不相同才合法{