寒光博客

[紫书]7.13 困难的串
困难的串(算法竞赛入门经典) 如果一个字符串包含两个相邻的重复子串,则称它是容易的串,其他串称为困难的串. 例如:...
扫描右侧二维码阅读全文
07
2019/08

[紫书]7.13 困难的串

困难的串(算法竞赛入门经典)

如果一个字符串包含两个相邻的重复子串,则称它是容易的串,其他串称为困难的串.
例如: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 (寒光博客)”原创,转载请保留文章出处。
Last modification:August 8th, 2019 at 12:48 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

14 comments

  1. dfs(“”)是什么鬼?

    1. Dxoca
      @灵

      初始化 空串

      1. @Dxoca

        φ( ̄∇ ̄o)好有特色。。。

        1. @灵

          l为10大概得多长时间,O阶是n^2log2(n)?

          1. Dxoca
            @灵

            和l 基本关系不大 ,,这个一直往下搜索,, 时间复杂度 我也不太会算 100的时候 还是A开头

            1. @Dxoca

              a打不打头不是n决定吗Σ(っ °Д °;)っ。l一样,输出所有困难串,谁打头不是都一样吗?可能我没读懂题。问一下,“D”不算l=4时的合法困难串吧!

              1. Dxoca
                @灵

                不是n 是 L(l=0 -->= "" l=1 -->A l=2 -->AB 3 ABC 4 ABCD),,,不管怎么样 都是从A开始 算 不过 可能D永远都不会出现,,,

                1. @Dxoca

                  l=2,n大于等于4的时候就不是a开了。l决定符合困难窜的数量,而n不是决定是第几个字典序吗?如果a在l一定时排完,就应该换字母了吧。可能我读不懂题

                  1. Dxoca
                    @灵

                    不会的额排不完的 永远 是A开头

            2. Dxoca
              @Dxoca

              三个字符(ABC) 基本 上k都轮不到B,,, 似乎 永远不会B

          2. @灵

            呼叫大佬,问一下静态博客更文后不刷新,有没有什么好方法显示新文

            1. Dxoca
              @灵

              Hexo么

              1. @Dxoca

        2. Dxoca
          @灵

          哈哈哈