最长回文串马拉车算法（Manacher）

#include <bits/stdc++.h>

using namespace std;

int main() {

    // # 马拉车算法

    // # 字符串扩展，每个字母间插入'0'，解决奇偶长度回文问题

    // s = '0' + '0'.join(list(s)) + '0'

    vector<char> s;

    char w;

    while ((w = getchar())!=EOF) {

        s.push_back('0');

        s.push_back(w);

    }

    s.push_back('0');

    int l = 0,r = 0;

    int n = s.size();

    // # 每个字母的臂长

    vector<int> m(n,0);

    // # 初始化，第0个字母臂长肯定是0，即自己

    // # m[0] = 0

    // '''

    // ddabacabac

    //      l ir

    //   2345678

    // m[li] = 1

    // ''' 

    // 前缀和优化

    vector<int> pre(n+1,0);

    if (s[0] == '1') {

        pre[1] = 1;

    }

    int li;

    for (int i = 1;i < n;i++) {

        if (s[i] == '1') {

            pre[i+1] = pre[i] + 1;

        }

        else {

            pre[i+1] = pre[i];

        }

        // # 在臂长范围中

        if (i < r) {

            // # 镜像i位置

            li = l - (i - l);

            // # 根据回文对称性，获取已知最短臂长

            m[i] = min(r-i,m[li]);

        }

        // # 暴力扩展

        while (i+m[i]+1 < n and i-m[i]-1 >= 0 and s[i+m[i]+1] == s[i-m[i]-1]) {

            m[i] += 1;

        }

        // # lr-box更新

        if (i + m[i] > r) {

            l = i;

            r = i + m[i];

        }

    }

    int res = pre[n];

    for (int i=0;i<n;i++) {

        // # 奇数回文中点不能为 1

        if (s[i] == '1') continue;

        l = i - m[i];

        r = i + m[i];

        //  [0,l) + [l,r] / 2 + [r+1,n]

        //  [l,r] 为回文子字符串，因此 1 个数减半

        res = min(res,pre[l] + (pre[r+1] - pre[l]) / 2 + pre[n] - pre[r+1]);

    }

    cout << res;

}