Найти самую длинную палиндромную подстроку, используя алгоритм Рабина-Карпа

Question

С https://algs4.cs.princeton.edu/53substring/

15. Самая длинная палиндромная подстрока. По заданной строке s найдите самую длинную подстроку, представляющую собой палиндром (или палиндром Уотсона-Крика).

Решение: может быть решено за линейное время, используя деревья суффиксов или алгоритм Манахера. Вот более простое решение, которое обычно работает в обычное время. Сначала мы опишем, как найти все палиндромные подстроки длины L точно в линейном времени: используйте Карп-Рабина, чтобы итеративно сформировать хеши каждой подстроки длины L (и ее обратной), и сравнить. Поскольку вы не знаете L, многократно удваивайте свои предположения о L, пока не узнаете, что оптимальная длина находится между L и 2L. Затем используйте бинарный поиск, чтобы найти точную длину.

Что я не понимаю, так это последняя часть.

Поскольку вы не знаете L, многократно удваивайте свои предположения о L, пока не узнаете, что оптимальная длина находится между L и 2L.

Как узнать, что такое "оптимальная" длина?

PS: вопрос о самой длинной палиндромной подстроке был задан ранее, но единственная, которая кажется полезной - это, и она также не использует Рабина-Карпа.

Изменить: это код, который я придумал на основе полученных ответов.

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;
}

Answer 1

Как только вы достигнете L для которого есть палиндромная подстрока длины L и нет палиндромной подстроки длины 2LВы знаете, что оптимальная длина между L а также 2L,

Два найти это вы используете бинарный поиск. Первая попытка L + ceil(L/2) если есть палиндромная подстрока этой длины, проделайте то же самое с L + ceil(L/2) а также 2LАналогичным образом, если нет палиндромной подстроки этой длины, ищите в [L, L + ceil(L/2)),