引言
在生物信息学、密码学和文本处理领域，经常需要比较循环同构的字符串。例如，DNA序列是环状的，从不同位置读取会得到不同的线性表示；在密码学中，寻找密钥的规范表示也涉及循环字符串的比较。最小表示法（Minimum Representation Algorithm）能够在O(n)线性时间内，找到循环字符串的所有旋转表示中字典序最小的一个。与朴素算法的O(n²)相比，这是一个质的飞跃。本文将深入讲解最小表示法的双指针追赶策略，并提供完整的Java实现。
问题建模
给定一个长度为n的字符串s，其循环旋转共有n种：
– 旋转0位：s[0], s[1], …, s[n-1]
– 旋转1位：s[1], s[2], …, s[n-1], s[0]
– 旋转2位：s[2], s[3], …, s[n-0], s[0], s[1]
– …
我们的目标是找到字典序最小的那个旋转，并返回其起始位置。
例如，对于字符串 "baca"：
– 旋转0："baca"
– 旋转1："acab"
– 旋转2："caba"
– 旋转3："abac"
字典序最小的是旋转3 "abac"，起始位置为3。
核心思想：双指针追赶与失配跳过
最小表示法使用两个指针 i 和 j 分别代表两个候选旋转的起始位置，用 k 记录当前已匹配的长度。
初始化 i = 0, j = 1, k = 0。
比较 s[(i+k)%n] 与 s[(j+k)%n]：
– 如果相等：k++，继续比较下一个字符。
– 如果 s[(i+k)%n] > s[(j+k)%n]：说明以 i 开头的旋转不可能是最小表示（因为在第k位已经更大），所以 i 可以跳过 i+k，即 i = i + k + 1。如果 i == j，则 i++。重置 k = 0。
– 如果 s[(i+k)%n] < s[(j+k)%n]：同理，j 可以跳过 j+k，即 j = j + k + 1。如果 i == j，则 j++。重置 k = 0。
当 i ≥ n 或 j ≥ n 或 k ≥ n 时结束。未被超过的那个指针即为答案。
这个算法的巧妙之处在于：一旦发现不匹配，就可以一次性跳过k+1个位置，而不是只移动一位。
Java实现
import java.util.*;
/**
* 最小表示法：在O(n)时间内找到循环字符串的字典序最小旋转
* 时间复杂度：O(n)，空间复杂度：O(1)
*/
public class MinimumRepresentation {
/**
* 最小表示法核心算法
* 返回字典序最小旋转的起始位置
* @param s 输入字符串（视为循环字符串）
* @return 最小旋转的起始下标
*/
public static int minimumRepresentation(String s) {
int n = s.length();
if (n == 0) return -1;
if (n == 1) return 0;
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
char a = s.charAt((i + k) % n);
char b = s.charAt((j + k) % n);
if (a == b) {
// 当前字符相等，继续比较下一位
k++;
} else if (a > b) {
// s[i..i+k] 不可能是最小表示，跳过
i = i + k + 1;
if (i <= j) {
i = j + 1; // 确保i > j，避免重复比较
}
k = 0;
} else {
// s[j..j+k] 不可能是最小表示，跳过
j = j + k + 1;
if (j <= i) {
j = i + 1;
}
k = 0;
}
}
return Math.min(i, j);
}
/**
* 获取最小表示对应的字符串
*/
public static String getMinRepresentation(String s) {
int pos = minimumRepresentation(s);
int n = s.length();
return s.substring(pos) + s.substring(0, pos);
}
/**
* 扩展：最大表示法（字典序最大的旋转）
* 只需将比较符号取反
*/
public static int maximumRepresentation(String s) {
int n = s.length();
if (n == 0) return -1;
if (n == 1) return 0;
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
char a = s.charAt((i + k) % n);
char b = s.charAt((j + k) % n);
if (a == b) {
k++;
} else if (a < b) {
// 注意这里符号相反：a < b 时i不可能最大
i = i + k + 1;
if (i <= j) i = j + 1;
k = 0;
} else {
j = j + k + 1;
if (j <= i) j = i + 1;
k = 0;
}
}
return Math.min(i, j);
}
/**
* 扩展：判断两个字符串是否循环同构
*/
public static boolean areCyclicallyEquivalent(String a, String b) {
if (a.length() != b.length()) return false;
if (a.isEmpty()) return true;
// b是否是a+a的子串
String doubled = a + a;
return doubled.contains(b);
}
/**
* 扩展：找出所有与最小表示相同的旋转位置
*/
public static List<Integer> findAllMinPositions(String s) {
List<Integer> result = new ArrayList<>();
String minStr = getMinRepresentation(s);
int n = s.length();
String doubled = s + s;
for (int i = 0; i < n; i++) {
if (doubled.substring(i, i + n).equals(minStr)) {
result.add(i);
}
}
return result;
}
/**
* 扩展：DNA序列环形比对中的最小表示应用
* 寻找环状DNA序列的规范表示
*/
public static String canonicalDNARepresentation(String dna) {
// DNA序列只包含A, C, G, T
// 同时考虑反向互补序列的最小表示
String minForward = getMinRepresentation(dna);
String reverseComp = reverseComplement(dna);
String minReverse = getMinRepresentation(reverseComp);
return minForward.compareTo(minReverse) <= 0 ? minForward : minReverse;
}
private static String reverseComplement(String dna) {
StringBuilder sb = new StringBuilder();
for (int i = dna.length() - 1; i >= 0; i--) {
sb.append(complement(dna.charAt(i)));
}
return sb.toString();
}
private static char complement(char c) {
return switch (c) {
case 'A' -> 'T';
case 'T' -> 'A';
case 'C' -> 'G';
case 'G' -> 'C';
default -> c;
};
}
public static void main(String[] args) {
// 测试1：基本最小表示
String s1 = "baca";
int pos1 = minimumRepresentation(s1);
System.out.println("字符串: " + s1);
System.out.println("最小旋转位置: " + pos1);
System.out.println("最小表示: " + getMinRepresentation(s1));
// 测试2：所有字符相同
String s2 = "aaaa";
System.out.println("\n字符串: " + s2);
System.out.println("最小旋转位置: " + minimumRepresentation(s2));
System.out.println("最小表示: " + getMinRepresentation(s2));
// 测试3：随机字符串
String s3 = "algorithm";
System.out.println("\n字符串: " + s3);
System.out.println("最小旋转位置: " + minimumRepresentation(s3));
System.out.println("最小表示: " + getMinRepresentation(s3));
System.out.println("最大表示: " + getMaxRepresentation(s3));
// 测试4：循环同构判断
String a = "abcd";
String b = "cdab";
System.out.println("\n" + a + " 与 " + b + " 循环同构? " + areCyclicallyEquivalent(a, b));
// 测试5：DNA规范表示
String dna = "ATCGATCG";
System.out.println("\nDNA序列: " + dna);
System.out.println("规范表示: " + canonicalDNARepresentation(dna));
}
private static String getMaxRepresentation(String s) {
int pos = maximumRepresentation(s);
int n = s.length();
return s.substring(pos) + s.substring(0, pos);
}
}
复杂度分析
- 时间复杂度：
O(n)。指针i和j以及k的总增量不超过3n，每个字符最多被访问常数次。 - 空间复杂度：
O(1)。仅使用3个整数变量，不依赖额外数组。
算法正确性证明要点
- 安全性：当
s[(i+k)%n] > s[(j+k)%n]时，对于任意t ∈ [i, i+k]，以t开头的旋转在第k-(t-i)位都大于以j+(k-(t-i))开头的旋转，因此这些位置都不可能是最小表示。 - 完备性：算法不会跳过潜在的最小表示候选，因为跳过的区间都已被证明不可能。
- 终止性：
i和j严格递增，最多在2n步内终止。
实际应用场景
- DNA序列比对：环状DNA的规范表示，消除旋转歧义
- 模式识别：图像轮廓的旋转不变特征提取
- 字符串哈希：将循环字符串统一映射到最小表示后再哈希
- 音乐信息检索：旋律的循环移位匹配
总结
最小表示法通过双指针的巧妙配合，将循环字符串字典序比较问题压缩到线性时间。其核心思想——失配时一次性跳过整个已匹配区间——体现了贪心策略在字符串算法中的强大威力。本文提供的Java实现涵盖了基本算法、最大表示、循环同构判断、DNA规范表示等扩展应用，可直接用于实际工程场景。
