马拉车算法 Manacher

简书

知乎

算法概述

首先把字符串进行填充，成为奇数长度的串

(p[i]) 表示以 (i) 为中心的最长回文串的半径

(id) 表示所有回文子串中能到最右端位置的那个串的中心位置

(mx) 最右端的位置

比较重要的几行代码

p[i] = i < mx ? min(mx-i,p[2*id-i]) : 1;

可以参考博客里的图片

int st = (cen - maxlen)/2;

maxlen = p[i]-1;

LeetCode模板

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if(n < 2)return s;
        string t = "$";
        for(int i = 0;i < n;i++){
            t += "#"+s.substr(i,1);
        }
        t += "#@";
        n = t.length();
        vector<int>p;p.resize(n+10);

        int id = 0,mx = 0;int maxlen = 0,cen = 0;
        for(int i = 1;i < n - 1;i++){
            p[i] = i < mx ? min(mx-i,p[2*id-i]) : 1;
            while(t[i-p[i]] == t[i+p[i]])p[i]++;
            if(i+p[i]>mx){
                mx = i+p[i];
                id = i;
            }
            if(p[i] - 1 > maxlen){
                maxlen = p[i]-1;
                cen = i;
            }
        }

        int st = (cen - maxlen)/2;
        return s.substr(st,maxlen);
    }
};