题解 | 密码截取：马拉车算法（O(n)时间复杂度）

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

int main() {
    string os;
    cin >> os;
    string s {"#"};
    for (auto c : os) {
        s += c;
        s += '#';
    }
    //求最长对称子序列的长度,中心拓展法(n2),马拉车算法(n)
    int n = s.size();
    vector<int> halfsize(n, 0);
    int maxright = 0;
    int maxmid = 0;
    int maxlen = 1;
    for (int mid = 1; mid < n ; mid++) {
        int left, right;
        left = right = mid;
        if (mid < maxright) {
            int leftmid = 2 * mid - maxmid;
            int maxleft = leftmid - halfsize[leftmid];
            right = min(maxright, 2 * maxmid - maxleft);
        }
        left = 2 * mid - right;
        while (left > 0 && right < n - 1 && s[left - 1] == s[right + 1]) {
            left -- ;
            right ++;
        }
        if (right > maxright) {
            maxmid = mid;
            maxright = right;
        }
        int halflen = right - mid;
        halfsize[mid] = halflen;
        maxlen = max(maxlen,halflen);
        if (right == n - 1) {
            break;
        }
    }
    cout << maxlen;
}