马拉车算法

manacher 算法

#include <bits/stdc++.h>
using namespace std;

string get_ss(string s){
    string ss = "$#";
    for(int i = 0;i<s.length();i++){
        ss+=s[i];
        ss+="#";
    }
    ss+="*";
    cout<<ss<<endl;
    return ss;
}
int manacher(string ss){
    int n = ss.length();
    int mx = 0;
    int id = 0;
    int MaxLeng = -1;
    vector<int> p(n,0);
    for(int i = 1;i<n-1;i++){
        if(mx>i){   
            p[i] = min(mx-i,p[id*2-i]);
        }
        else {
            p[i]=1;
        }

        while(ss[i+p[i]]==ss[i-p[i]]){
            p[i]++;
        }

        if(mx<p[i]+i){
            mx = p[i]+1;
            id = i;
        }
        MaxLeng= max(MaxLeng,p[i]-1);
    }
    return MaxLeng;
}

int main(){
    string s ;
    cin>>s;
    string ss = get_ss(s);
    cout<<manacher(ss)<<endl;
    return 0;
}

5. 最长回文子串

class Solution {
public:
    string ret="";
    string get_ss(string s){
        string ss = "$#";
        for(int i = 0;i<s.length();i++){
            ss+=s[i];
            ss+="#";
        }
        ss+="*";
        // cout<<ss<<endl;
        return ss;
    }
    void manacher(string ss){
        int n = ss.length();
        int mx = 0;
        int id = 0;
        int MaxLeng = -1;
        vector<int> p(n,0);
        for(int i = 1;i<n-1;i++){
            if(mx>i){   
                p[i] = min(mx-i,p[id*2-i]);
            }
            else {
                p[i]=1;
            }

            while(ss[i+p[i]]==ss[i-p[i]]){
                p[i]++;
            }

            if(mx<p[i]+i){
                mx = p[i]+1;
                id = i;
            }
            if(MaxLeng<=p[i]-1){
                MaxLeng= max(MaxLeng,p[i]-1);
                ret = ss.substr(i-p[i]+2,MaxLeng*2);
            }
        }
        // cout<<MaxLeng<<endl;
        // return MaxLeng;
    }

    string longestPalindrome(string s) {
        string ss = get_ss(s);
        manacher(ss);
        string ans = "";
        for(int i = 0;i<ret.length();i++){
            if(ret[i]!='#'){
                ans+=ret[i];
            }
        }
        return ans;
    }
};