1 条题解

  • 0
    @ 2023-11-11 16:39:03
    #include <bits/stdc++.h>
    using namespace std;
    string tempS, s;
    int P[112345 * 2];
    // 以 i 开头的最长回文串
    int f[112345 * 2];
    // 以 i 结尾的最长回文串
    int g[112345 * 2];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> tempS;
        s = "^";
        s += "#";
        for (int i = 0; i < tempS.length(); i++)
            s += tempS[i], s += "#";
        s += "$";
        int n = s.length();
        // manacher
        int C, R;
        C = R = 0;
        for (int i = 1; i < n - 1; i++)
        {
            int i_mirror = 2 * C - i; // C - i_mirror = i - C
            if (R > i)
                P[i] = min(R - i, P[i_mirror]);
            else
                P[i] = 0;
            while (s[i + P[i] + 1] == s[i - P[i] - 1])
                P[i]++;
            f[i - P[i]] = max(f[i - P[i]], P[i]);
            g[i + P[i]] = max(g[i + P[i]], P[i]);
            if (i + P[i] > R)
            {
                C = i;
                R = i + P[i];
            }
        }
        for (int i = 3; i <= n - 2; i++)
            f[i] = max(f[i], f[i - 2] - 2);
        for (int i = n - 4; i >= 1; i--)
            g[i] = max(g[i], g[i + 2] - 2);
        /*
        cout << s << endl;
        for (int i = 0; i < n; i++)
            cout << P[i];
        cout << endl;
        for (int i = 0; i < n; i++)
            cout << f[i];
        cout << endl;
        for (int i = 0; i < n; i++)
            cout << g[i];
        cout << endl;
        */
        int ans = 0;
        for (int i = 1; i <= n - 2; i++)
            if (s[i] == '#' && f[i] && g[i])
                ans = max(ans, f[i] + g[i]);
        cout << ans << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    1359
    时间
    1000ms
    内存
    125MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者