## Saturday, December 19, 2015

### Longest Palindromic Substring - Manacher

http://shirleyisnotageek.blogspot.com/2014/12/longest-palindromic-substring-dp-on.html
The complete explanation of this O(n) solution, which is called, Manacher's Algorithm can be found here. I will just simplify it based on my understanding.

So consider we have a string s = "aabab". How can we check every substring using iteration? We need to check "aa", "aab", "aaba", "aabab", then "aba" ... and so on. Then this will be O(n^2), we are not doing anything better. But, what if we add something into the string:

# a # a # b # a # b #
0   1  2  3  4   5  6   7  8   9  10

Well, whatever symbol you would like to use is fine. The point is, now we double the length of the string, and every substring of s is symmetric in the new string. If we want to check "aa", it is symmetric against "#", "aba" is symmetric against "b". Thus, by iterate through the new string, we can check every substring of s in linear time.
`    ``public` `String longestPalindrome(String s) {`
`        ``if` `(s == ``null` `|| s.length() == 0)`
`            ``return` `""``;`
`        ``int` `maxSubstring = 1;`
`        ``String rst = s.substring(0, 1);`
`        ``for` `(``int` `i = 1; i <= 2 * s.length() - 1; i++) {`
`            ``int` `count = 1;`
`            ``while` `(i - count >=  0 && i + count <= 2 * s.length() && `
` get``(s, i - count) == ``get``(s, i + count)) {`
`                ``count++;`
`            ``}`
`            ``//Note that since "#" always equals "#", we will have an extra count for each substring`
`            ``count--;`
`            ``if` `(count > maxSubstring) {`
`                ``maxSubstring = count;`
`                ``rst = s.substring((i - count) / 2, (i + count) / 2);`
`            ``}`
`        ``}`
`        ``return` `rst;`
`    ``}`
`        ``private` `char` `get``(String s, ``int` `index) {`
`            ``if` `(index % 2 == 0)`
`                ``return` `'#'``;`
`            ``else`
`                ``return` `s.charAt(index / 2);`
`        ``}`
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html