5-5 无分隔符字典问题

---

问题描述

设∑=(α1,α2,...,αn)∑=(α1,α2,...,αn)<script type="math/tex" id="MathJax-Element-1">\sum=(\alpha_1,\alpha_2,...,\alpha_n)</script>是 n 个互不相同的符号组成的符号集。
Lk={β1β2...βk|βi∈∑,1≤i≤k}Lk={β1β2...βk|βi∈∑,1≤i≤k}<script type="math/tex" id="MathJax-Element-2">L_k=\{\beta_1\beta_2...\beta_k|\beta_i\in\sum,1\leq i\leq k\}</script>是∑∑<script type="math/tex" id="MathJax-Element-3">\sum</script>中字符组成的长度为k的全体字符串。 S⊆LkS⊆Lk<script type="math/tex" id="MathJax-Element-4">S\subseteq L_k</script>是LkLk<script type="math/tex" id="MathJax-Element-5">L_k</script>的1个无分隔符字典是指对任意a1a2...ak∈Sa1a2...ak∈S<script type="math/tex" id="MathJax-Element-6">a_1a_2...a_k\in S</script>和b1b2...bk∈Sb1b2...bk∈S<script type="math/tex" id="MathJax-Element-7">b_1b_2...b_k\in S</script>，则

<script type="math/tex; mode=display" id="MathJax-Element-8">\{a_2a_3...a_kb_1,a_3a_4...b_1b_2,...,a_kb_1b_2...b_{k-1}\}\bigcap S=\emptyset</script>

无分隔符字典问题要求对给定的 n, ∑∑<script type="math/tex" id="MathJax-Element-9">\sum</script>以及正整数 k，编程计算 LkLk<script type="math/tex" id="MathJax-Element-10">L_k</script> 的最大无分隔符字典。

设计一个算法，对于给定的正整数 n 和 k，编程计算 LkLk<script type="math/tex" id="MathJax-Element-11">L_k</script> 的最大无分隔符字典。

数据输入：
第一行有 2 个正整数 n 和 k。

---

Java

package Chapter5HuiSuFa;

import java.util.*;

public class WuFenGeFuZiDian {

    private static int n, k;
    private static int[] ak;
    private static int lk;
    private static int[] x;
    private static int best;

    private static int MAX = 10000;
    private static Set<Integer> S;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        while (true) {
            best = 0;

            n = input.nextInt();
            k = input.nextInt();

            S = new HashSet<>(MAX);
            ak = new int[2*k];
            x = new int[n+1];
            lk = n;

            for (int i=1; i<=n; i++)
                x[i] = i;

            for (int i=1; i<k; i++)
                lk *= n;
            lk--;

            if(k < 3) {
                System.out.println(n);
                continue;
            }

            search(0);

            System.out.println(best);
        }
    }

    //将相应字符串转换为n进制数
    private static int digi(int i) {
        int ii = k+i-2;
        int x = ak[ii--];
        for (int j=0; j<k-1; j++) {
            x *= n;
            x += ak[ii];
            ii--;
        }
        return x;
    }

    //判断字符串a和b是否互不为前缀
    private static boolean pref(int a, int b) {
        int x = a;
        int y = b/n;
        for (int i=0; i<k-1; i++){
            ak[k-i-2] = x%n;
            x /= n;
            ak[2*k-i-3] = y%n;
            y /= n;
        }
        for (int i=1; i<k; i++)
            if (S.contains(digi(i)))
                return true;

        x = b;
        y = a/n;
        for (int i=0; i<k-1; i++) {
            ak[k-i-2] = x%n;
            x /= n;
            ak[2*k-i-3] = y%n;
            y /= n;
        }
        for (int i=1; i<k; i++)
            if (S.contains(digi(i)))
                return true;

        return false;
    }

    //判断当前字符串b是否可以加入字典
    //将字符串a1a2..ak看作k位n进制数
    private static boolean oka(int b) {
        Iterator<Integer> it = S.iterator();
        while (it.hasNext()) {
            int a = it.next();
            if (pref(a, b))
                return false;
        }

        return true;
    }

    //逐步加深的回溯法
    private static void search(int dep) {
        if (dep > lk) {
            if (S.size() > best)
                best = S.size();
            return;
        }
        if (oka(dep)) {
            S.add(dep);
            search(dep + 1);
            S.remove(dep);
        }
        search(dep + 1);
    }
}

Input & Output

2 2
2

16 2
16

Reference

王晓东《计算机算法设计与分析》（第3版）P181