困难的串(算法竞赛入门经典)
如果一个字符串包含两个相邻的重复子串,则称它是容易的串,其他串称为困难的串.
例如: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;
}
}
本文地址: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么
嗯
哈哈哈