来自https://algs4.cs.princeton.edu/53substring/
15. 最长回文子串。给定一个字符串 s,找出最长的子串,它是一个回文(或 Watson-crick 回文)。
解决方案:可以使用后缀树或 Manacher 算法在线性时间内求解。这是一个更简单的解决方案,通常在线性时间内运行。首先,我们描述如何在线性时间内找到长度正好为 L 的所有回文子串:使用 Karp-Rabin 迭代地形成每个长度为 L 的子串(及其反向)的哈希值,并进行比较。因为你不知道 L,所以重复你对 L 的猜测,直到你知道最佳长度在 L 和 2L 之间。然后使用二进制搜索找到确切的长度。
我不明白的是最后一部分。
因为你不知道 L,所以重复你对 L 的猜测,直到你知道最佳长度在 L 和 2L 之间。
我怎么知道“最佳”长度是多少?
PS:最长回文子串的问题之前已经问过,但似乎唯一有用的是this,它也没有使用Rabin-Karp。
编辑:这是我根据收到的答案提出的代码。
public static String longestPalindrome(String key) {
int r = 256;
long q = longRandomPrime();
boolean lastFound;
boolean found;
int l = 2;
do {
lastFound = indexOfPalindromeOfGivenLength(key, l, r, q) >= 0;
l *= 2;
found = indexOfPalindromeOfGivenLength(key, l, r, q) >= 0;
} while (l < key.length() && !(lastFound && !found));
int left = l / 2;
int right = l;
while (left <= right) {
System.out.printf("Searching for palindromes with length between: %d and %d%n", left, right);
int i = indexOfPalindromeOfGivenLength(key, left, r, q);
lastFound = i >= 0;
int j = indexOfPalindromeOfGivenLength(key, right, r, q);
found = j >= 0;
if (lastFound && found) return key.substring(j, j + right);
int x = left + (right - left) / 2;
if (!found) right = x;
else left = x;
}
return null;
}
private static int indexOfPalindromeOfGivenLength(String key, int l, int r, long q) {
System.out.printf("Searching for palindromes with length: %d%n", l);
for (int i = 0; i + l <= key.length(); i++) {
String s1 = key.substring(i, i + l);
long h1 = hash(s1, r, q);
long h2 = hash(new StringBuilder(s1).reverse().toString(), r, q);
if (h1 == h2) {
System.out.printf("Found palindrome: %s of length: %d%n", s1, s1.length());
return i;
}
}
System.out.printf("No palindromes of length %d exist%n", l);
return -1;
}