题解 | #最长回文子串#

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string preprocess(const string &s){
    string res="^#";
    for(char c:s){
        res=res+c+'#';
    }
    res+='$';
    return res;
}

int maxLengthPalin(const string &s){
    string s1=preprocess(s);
    int len=s1.length();
    vector<int> record(len);
    int c=0,r=0,maxL=1;
    for(int i=0;i<len;++i){
        int mirror=2*c-i;
        int j=min(record[mirror],r-i);
        while(i-j-1>=0 && i+j+1<len && s1[i-j-1]==s1[i+j+1])
            ++j;
        record[i]=j;
        maxL=max(maxL,j);
        if(i+j>r){
            c=i;
            r=i+j;
        }
    }
    return maxL;
}

int main() {
    string s;
    cin>>s;
    cout<<maxLengthPalin(s);
}
// 64 位输出请用 printf("%lld")

Manacher算法

利用镜像位置的最长半径来初始化半径，再向外拓展。

复杂度是O(n)O(n)