困难的串(算法竞赛入门经典)
如果一个字符串包含两个相邻的重复子串,则称它是容易的串,其他串称为困难的串.
例如:BB,ABCDACABCAB,ABCDABCD都是容易的，而D、DC、ABDAB、CBABCBA都是困难的。
输入正整数n和L,输出由前L个字符组成的,字典序第n小的困难的串.
例如，当L=3时，前7个困难的串分别为:
A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。
输入保证答案不超过80个字符
输入:
7 3
30 3输出:
ABACA BA
ABACA BCACB ABCAB ACABC ACBAC ABA分析:
从左到右一次考虑每位置上的字符。关键：
如何判断当前字符串是否存在连续的重复子串。例如，如何判断ABACABA是否包含连续重复子串呢?
方法1：检查所有长度为偶数的子串，判断前一半=后一半
方法2:只需判断当前串的后缀
我使用方法二，因为跟高效，前缀一定是符合要求的 isHard()
类似n皇后：只判断当前皇后与之前的皇后是否冲突，而不判断之前的皇后是否互相冲突
代码
package BlueCup.Seven_recursion;
import java.util.Scanner;
public class Dfs6空困难的串 {
static int n;
static int l;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();//第n个困难
l = cin.nextInt();//前几个字符
dfs("");
}
static int count = 0;
private static void dfs(String prefix) {
//尝试在每个prefix后面追加一个字符
for (char i = 'A'; i < 'A' + l; i++) {
if (isHard(prefix, i)) {//难点
String x = prefix + i;
System.out.println(x);//输出[0,n) n-1就是最后一个了
count++;
if (count == n) {
System.exit(0);
}
dfs(x);//继续搜索
}
}
}
/**
* 判断 是否有 两个相邻的重复子串
* 即判断 prefix+i是否是困难的字符串
* 方法1：检查所有长度为偶数的子串，判断前一半=后一半 相比二 效率低下 因为前面的绝对是困难的串
* 方法2:只需判断当前串的后缀 减少不必要的判断
* @param prefix 旧串
* @param i 要加进去的字符
* @return
*/
private static boolean isHard(String prefix, char i) {
int width = 0;//截取的宽度
for (int j = prefix.length() - 1; j >= 0; j -= 2) {
final String s1 = prefix.substring(j, j + width + 1);//[)前缀 后缀
final String s2 = prefix.substring(j + width + 1) + i;//[]
if (s1.equals(s2)) return false;//有相同 不符合
width++;
}
return true;
}
}
本文作者：Author： 寒光博客
文章标题：[紫书]7.13 困难的串
本文地址：https://dxoca.cn/Algorithm/226.html 百度未收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/Algorithm/226.html 百度未收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
dfs(“”)是什么鬼？
初始化 空串
φ(￣∇￣o)好有特色。。。
l为10大概得多长时间,O阶是n^2log2(n)?
和l 基本关系不大 ，，这个一直往下搜索，， 时间复杂度 我也不太会算 100的时候 还是A开头
a打不打头不是n决定吗Σ(っ °Д °;)っ。l一样，输出所有困难串，谁打头不是都一样吗?可能我没读懂题。问一下，“D”不算l=4时的合法困难串吧！
不是n 是 L（l=0 -->= "" l=1 -->A l=2 -->AB 3 ABC 4 ABCD），，，不管怎么样 都是从A开始 算 不过 可能D永远都不会出现，，，
l=2,n大于等于4的时候就不是a开了。l决定符合困难窜的数量，而n不是决定是第几个字典序吗？如果a在l一定时排完，就应该换字母了吧。可能我读不懂题
不会的额排不完的 永远 是A开头
三个字符（ABC） 基本 上k都轮不到B,,, 似乎 永远不会B
呼叫大佬，问一下静态博客更文后不刷新，有没有什么好方法显示新文
Hexo么
嗯
哈哈哈