LeetCode Longest Palindrome

leetcode 题目描述 戳这里

hihocoder 题目描述 戳这里

这个题目看了很多次了一直没有想出O(n)的解法,搜hihoCoder题解的时候无意发现了这个Manacher算
法,用来处理最长回文子字符串

原理如下,图片来源自OSChina的博客

算法做了简化处理,为了让所有字符都可以作为一个回文字符串的中心字符
ababa这样的字符串变成#a#b#a#b#a#, bb变成#b#b#

为什么要这样呢?

cddc这种回文字符串是不是没有中心?aba这种有中心,你很难判断,都化成有中心的,
那就简单多了

每个中心字符就是原字串里的字符或者’#’

然后用一个数组p[2 len + 1],p[i]表示i处为中心的回文字符串长度+1,
其实就是半径,并包含了中心原点,包含#符号的回文长度是2 * r - 1

实际长度real应该是r - 1

举个栗子

#a#b#c#b#a#的中心字符是c,半径r是6,总长度len是11,实际长度是5,符合上面的关系
#b#b#b#b#的中心字符是#,半径r是5,总长度len是9,实际长度是4,符合上面关系

注意:中心字符是#的情况,最两边一定是#,#和#肯定是相等的,所以match到最后一个有效字符之后还会继续match最后一个#字符

len是字符串长度,id从1开始,1是第一个有效字符的起始点

for (int i = 1; i < len; i++) {
    if (mx > i)
        p[i] = min(p[id * 2 - i], mx - i);
    else
        p[i] = 1;
    while ((p[i] + i < len) && (i - p[i] >= 0) && (str[ i - p[i] ] == str[ i + p[i] ]))
        p[i]++;
    if (p[i] + i > mx) {
        mx = i + p[i];
        id = i;
    }
}

(p[i] + i < len) && (i - p[i] >= 0)是为了保证不越界,后面是开始从当前节点开始计算p[i]长度



为了能看懂下面的公式,你要注意一个细节:
那就是id * 2 = i + j,明白吗?因为id是i和j的中点,自然等于他俩和的1/2啦

下面两图解释了为什么p[i] = min(p[id * 2 - i], mx - i)要取min值,因为mx - i可能比p[j] (即p[id * 2 - i])要小,因为到达了mx处后面的还没有比较,以j为中心的回文串长度放到以i为中心时,半径超越了mx

看到下面那个多余出来的蓝色吗?那是处理过的,但mx点以后,你并不清楚啊



然后找出最大的p[i] - 1就是最大长度

题目描述

Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there
exists one unique longest palindromic substring.

下面给出leetcode的代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return s;
        string str;
        int len = s.size() * 2 + 1;
        str.resize(len);
        str[0] = '#';
        for (int i = 0; i < s.size(); i++) {
            str[i * 2 + 1] = s[i];
            str[i * 2 + 2] = '#';
        }
        int p[len];
        p[0] = 1;
        int mx = 0;
        int id = 1;
        for (int i = 1; i < len; i++) {
            if (mx > i)
                p[i] = min(p[id * 2 - i], mx - i);
            else
                p[i] = 1;
            while ((p[i] + i < len) && (i - p[i] >= 0) && (str[ i - p[i] ] == str[ i + p[i] ]))
                p[i]++;
            if (p[i] + i > mx) {
                mx = i + p[i];
                id = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (ans < p[i] - 1) {
                ans = p[i] - 1;
                id = i;
            }
        }

        string pli;
        for (int i = id - ans + 1; i < id + ans; i++)
            if (str[i] != '#') pli += str[i];

        return pli;
    }
};

哎第一份正式解题报告。。。sugaoyi!

编程之美2015的第二题,要求的东西跟这个很像,但你知道具体他要求啥?呵呵,不告诉你