CODEWITHSUNDEEP
javastringalgorithmdata-structuresrabin-karp
Abhijit Sarkar
Abhijit Sarkar

Reputation: 24518

Find longest palindromic substring using Rabin-Karp algorithm

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

15. Longest palindromic substring. Given a string s, find the longest substring that is a palindrome (or a Watson-crick palindrome).

Solution: can be solved in linear time using suffix trees or Manacher's algorithm. Here's a simpler solution that typically runs in linearthmic time. First, we describe how to find all palindromic substrings of length exactly L in linear time: use Karp-Rabin to iteratively form the hashes of each substring of length L (and its reverse), and compare. Since you don't know L, repeatedly double your guess of L until you know the optimal length is between L and 2L. Then use binary search to find the exactly length.

What I don't understand is the last part.

Since you don't know L, repeatedly double your guess of L until you know the optimal length is between L and 2L.

How do I know what's the "optimal" length?

P.S.: The question of longest palindromic substring has been asked before, but the only one that seems to be useful is this, and it too doesn't use Rabin-Karp.

Edit: This is the code I came up with based on the answers received.

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

Upvotes: 2

Views: 2900

Answers (1)

Yola
Yola

Reputation: 19019

As soon as you reach L for which there is a palindromic substring of length L and no palindromic substring of length 2L, you know that optimal length is between L and 2L.

Two find it you use binary search. First try L + ceil(L/2) if there is palindromic substring of this length do the same with L + ceil(L/2) and 2L, similarly if if there is no palindromic substring of this length, then search in [L, L + ceil(L/2)).

Upvotes: 2

Related Questions