Content deleted Content added
→Manacher's algorithm: A simpler way of expressing the intent of the comparison. The other way doesn't make sense for cases where the index type is unsigned. |
→Slow algorithm: Copyedit. |
||
Line 6:
The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic [[subsequence]].
==
This algorithm is slower than Manacher's algorithm, but is a good stepping stone for understanding Manacher's algorithm. It looks at each character as the center of a palindrome and loops to determine the largest palindrome with that center.
The loop at the center of the function only works for palindromes where the length is an odd number. The function works for even-length palindromes by modifying the input string. The character '|' is inserted between every character in the inputs string, and at both ends. So the input "book" becomes "|b|o|o|k|". The even-length palindrome "oo" in "book" becomes the odd-length palindrome "|o|o|".
Longest_Palindrome_SLOW(string S, string S') {
| |||