string - 使用Rabin-Karp算法查找最长回文子串

从https://algs4.cs.princeton.edu/53substring/
15岁最长的回文子串。给定一个字符串s，找出最长的
是回文的子串（或watson crick回文）。
解决方案：可以使用后缀树或
马纳彻的算法。下面是一个简单的解决方案，通常在
线性时间。首先，我们描述如何找到所有的回文。
线性时间中长度为L的子串：使用Karp-Rabin
迭代形成长度为l的每个子串的散列（及其
相反），并进行比较。既然你不认识我，就再重复一次
在你知道最佳长度在L和2L之间之前，一直猜L。然后
使用二进制搜索查找确切的长度。
我不明白的是最后一部分。
既然你不认识我，就不断地加倍你对我的猜测直到你
知道最佳长度在L和2L之间。
我怎么知道“最佳”长度是多少？
注：最长回文子串的问题以前也有人问过，但唯一有用的似乎是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;
}

最佳答案

当您到达L时，如果有一个长度L的回文子串并且没有长度2L的回文子串，您就知道最佳长度在L和2L之间。
二用二进制搜索找到它。首先尝试L + ceil(L/2)如果有此长度的回文子串，请使用L + ceil(L/2)和2L执行相同的操作；同样，如果没有此长度的回文子串，请在[L, L + ceil(L/2))中搜索。

关于string - 使用Rabin-Karp算法查找最长回文子串，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50852865/