问题描述
设∑=(α1,α2,…,αn)是 n 个互不相同的符号组成的符号集。 Lk={β1β2…βk|βi∈∑,1≤i≤k}是∑中字符组成的长度为k的全体字符串。 S⊆Lk是Lk的1个无分隔符字典是指对任意a1a2…ak∈Sa1a2…ak∈S和b1…bk∈S则 {a2a3…akb1,a3a4…b1b2,…,akb1b2…bk−1}⋂S=∅ 无分隔符字典问题要求对给定的 n, ∑以及正整数 k，编程计算 Lk 的最大无分隔符字典。
设计一个算法，对于给定的正整数 n 和 k，编程计算 Lk的最大无分隔符字典。
数据输入： 第一行有 2 个正整数 n 和 k。
代码展示
package algorithm;
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;
private static Set<Integer> res;
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);
res = 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--;
search(0);
System.out.println("当前最大无分隔符字典元素数量为：");
System.out.println(best);
System.out.println("最大字典集合:"+res);
}
}
//ii是a1a2...akb1b2...bk-1的bi的下标。i-1是bi为结尾的字符串开始的位置。
private static int digi(int i) {
int ii = k+i-2;
int x = ak[i-1];
for (int j=0; j<k-1; j++) {
x *= n;
x += ak[i];
i++;
}
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;
}
private static boolean oka(int b) {
S.add(b);
for (Integer a : S) {
if (a != b && pref(a, b)) {
S.remove(b);
return false;
}
}
return true;
}
//逐步加深的回溯法
private static void search(int dep) {
if (dep > lk) {
if (S.size() > best) {
best = S.size();
res.clear();
res.addAll(S);
}
return;
}
if (oka(dep)) {
S.add(dep);
search(dep + 1);
S.remove(dep);
}
search(dep + 1);
}
}
