题解 | #最长回文子串#

manacher

#include <iostream>
#include <vector>
using namespace std;


int manacher(string str) {
    // a b
    // $*a*b*^
    // $*a*b*a*^

    string astr;
    astr += '$';

    int ret = 1;
    for ( auto c: str)
        astr += '*',astr += c;
    astr += '*',astr += '^';

    vector<int> p_len(astr.size(), 1);
    int a_sz = astr.size();

    int center = 0;
    for ( int i = 1; i < a_sz; ++i) {
        int lb = 2 * center - i;
        int exLen = min(center + p_len[center] - i, p_len[lb]);

        
        int l = i - p_len[i];
        int r = i + p_len[i];

        while ( ~l && r < a_sz && astr[l] == astr[r]) {
            p_len[i]++;
            --l;
            ++r;
        }
        // cout << p_len[i] << " ";
        ret = max(p_len[i] - 1, ret);
        if ( r >= center + p_len[center]) {
            center = i;
        }
    }


    return ret;
}
int main() {
    
    string str;
    getline(cin, str);

    int ans = manacher(str);

    cout << ans;

    return 0;
}
// 64 位输出请用 printf("%lld")