Longest palindromic substring

In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring.

Manacher (1975) invented a linear time algorithm for listing all the palindromes that appear at the start of a given string. However, as observed e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in linear time. Therefore, it provides a linear time solution to the longest palindromic substring problem. Alternative linear time solutions were provided by Jeuring (1994), and by Gusfield (1997), who described a solution based on suffix trees. Efficient parallel algorithms are also known for the problem.[1]

The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic subsequence.

Manacher's algorithm

To find a longest palindrome in a string in linear time, an algorithm may take advantage of the following characteristics or observations about a palindrome and a sub-palindrome:

  1. The left side of a palindrome is a mirror image of its right side.
  2. (Case 1) A third palindrome whose center is within the right side of a first palindrome will have exactly the same length as a second palindrome anchored at the mirror center on the left side, if the second palindrome is within the bounds of the first palindrome by at least one character (not meeting the left bound of the first palindrome). Such as "dacabacad", the whole string is the first palindrome, "aca" in the left side as second palindrome, "aca" in the right side as third palindrome. In this case, the second and third palindrome have exactly the same length.
  3. (Case 2) If the second palindrome meets or extends beyond the left bound of the first palindrome, then the distance from the center of the second palindrome to the left bound of the first palindrome is exactly equal to the distance from the center of the third palindrome to the right bound of the first palindrome.
  4. To find the length of the third palindrome under Case 2, the next character after the right outermost character of the first palindrome would then be compared with its mirror character about the center of the third palindrome, until there is no match or no more characters to compare.
  5. (Case 3) Neither the first nor second palindrome provides information to help determine the palindromic length of a fourth palindrome whose center is outside the right side of the first palindrome.
  6. It is therefore desirable to have a palindrome as a reference (i.e., the role of the first palindrome) that possesses characters farthest to the right in a string when determining from left to right the palindromic length of a substring in the string (and consequently, the third palindrome in Case 2 and the fourth palindrome in Case 3 could replace the first palindrome to become the new reference).
  7. Regarding the time complexity of palindromic length determination for each character in a string: there is no character comparison for Case 1, while for Cases 2 and 3 only the characters in the string beyond the right outermost character of the reference palindrome are candidates for comparison (and consequently Case 3 always results in a new reference palindrome while Case 2 does so only if the third palindrome is actually longer than its guaranteed minimum length).
  8. For even-length palindromes, the center is at the boundary of the two characters in the middle.


Pseudocode

 
    given string S
    string S' = S with a bogus character (eg. '|') inserted between each character (including outer boundaries)
    array P = [0,...,0] // To store the lengths of the palindrome for each center point in S'
    // note: length(S') = length(P) = 2 × length(S) + 1
    
    // Track the following indices into P or S'
    R = 0 // The next element to be examined; index into S
    C = 0 // The largest/left-most palindrome whose right boundary is R-1; index into S
    i = 1 // The next palindrome to be calculated; index into P
    define L  = i − (R − i) // Character candidate for comparing with R; index into S
    define i' = C − (i − C) // The palindrome mirroring i from C; index into P
    
    while R < length(S'):
        If i is within the palindrome at C (Cases 1 and 2):
            Set P[i] = P[i'] // note: recall P is initialized to all 0s
    
            // Expand the palindrome at i (primarily Cases 2 and 3; can be skipped in Case 1,
            // though we have already shown that S'[R] ≠ S'[L] because otherwise the palindrome
            // at i' would have extended at least to the left edge of the palindrome at C):
            while S'[R] == S'[L]:
                increment P[i]
                increment R
    
        If the palindrome at i extends past the palindrome at C:
            update C = i
    
        Else increment i
    
    return max(P)

This diverges a little from Manacher's original algorithm primarily by deliberately declaring and operating on R in such a way to help show that the runtime is in fact linear. You can see in the pseudo-code that R, C and i are all monotonically increasing, each stepping through the elements in S' and P. (the end condition was also changed slightly to not compute the last elements of P if R is already at the end - these will necessarily have lengths less than P[C] and can be skipped).

The use of S' provides a couple of simplifications for the code: it provides a string aligned to P allowing direct use of the pointers in both arrays and it implicitly enables the inner while-loop to double-increment P[i] and R (because every other time it will be comparing the bogus character to itself).

Notes
  1. Crochemore & Rytter (1991), Apostolico, Breslauer & Galil (1995).

References
  • Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), "Parallel detection of all palindromes in a string", Theoretical Computer Science, 141 (1–2): 163–173, doi:10.1016/0304-3975(94)00083-U.
  • Crochemore, Maxime; Rytter, Wojciech (1991), "Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays", Theoretical Computer Science, 88 (1): 59–82, doi:10.1016/0304-3975(91)90073-B, MR 1130372.
  • Crochemore, Maxime; Rytter, Wojciech (2003), "8.1 Searching for symmetric words", Jewels of Stringology: Text Algorithms, World Scientific, pp. 111–114, ISBN 978-981-02-4897-0.
  • Gusfield, Dan (1997), "9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences, Cambridge: Cambridge University Press, pp. 197–199, doi:10.1017/CBO9780511574931, ISBN 0-521-58519-8, MR 1460730.
  • Jeuring, Johan (1994), "The derivation of on-line algorithms, with an application to finding palindromes", Algorithmica, 11 (2): 146–184, doi:10.1007/BF01182773, hdl:1874/20926, MR 1272521, S2CID 7032332.
  • Manacher, Glenn (1975), "A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string", Journal of the ACM, 22 (3): 346–351, doi:10.1145/321892.321896, S2CID 10615419.
This article incorporates text from Longest palindromic substring on PEGWiki under a Creative Commons Attribution (CC-BY-3.0) license.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.