Prefix-Suffix Palindrome (Hard version) [Codeforces Global Round 7 D2]

https://codeforces.com/contest/1326/problem/D2

前提知識

• Manacher

解説

https://codeforces.com/contest/1326/submission/73898734

高速にクエリをさばいていこう。

文字列のprefixとsuffixで回文となる最大長を計算しておく。
この最大長以下であれば、どれも回文となる。
prefix+回文+suffixで回文になるように、真ん中の回文を全探索しよう。
manacherを使えば、中心からの回文の長さが分かる。
これを使おう。
ある中央から、なるべく長い回文を選んだ時に、最大のprefix, suffixとかぶっているか確認する。
これがかぶっていれば、prefix, suffixを調整することで、答えの候補が得られる。
この中で長さが最も長いものを選択すると答え。

アルゴリズムは難しくないが、実装が大変。

int T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T;
    rep(_, 0, T) {
        string s; cin >> s;
        int n = s.size();

        int len = 0;
        rep(i, 0, n) {
            if (s[i] != s[n - 1 - i]) break;
            len++;
        }

        string ss = "";
        rep(i, 0, n - 1) ss += s.substr(i, 1) + "a";
        ss += s[n - 1];
        auto mv = manacher(ss);

        int ans1 = 0;
        int pre1 = 0;
        int L1 = -1, R1 = -1;
        rep(i, 1, n - 1) {
            int ma = (mv[i * 2] - 1) / 2;
            // [i - ma, i + ma]

            int lft = i - ma;
            int rht = n - (i + ma) - 1;

            if (min(lft, rht) <= len) {
                int len = min(lft, rht) * 2 + ma * 2 + 1;
                if (ans1 < len) {
                    ans1 = len;
                    pre1 = min(lft, rht);
                    L1 = i - ma;
                    R1 = i + ma;
                }
            }
        }

        rep(i, 0, n - 1) {
            int ma = mv[i * 2 + 1] / 2;
            // [i - ma + 1, i + ma]

            int lft = i - ma + 1;
            int rht = n - (i + ma) - 1;

            if (min(lft, rht) <= len) {
                int len = min(lft, rht) * 2 + ma * 2;
                if (ans1 < len) {
                    ans1 = len;
                    pre1 = min(lft, rht);
                    L1 = i - ma + 1;
                    R1 = i + ma;
                }
            }
        }

        string ans = "";

        if (ans1 == 0) {
            ans = s.substr(0, 1);
        }
        else {
            ans = s.substr(0, pre1) + s.substr(L1, R1 - L1 + 1) + s.substr(n - pre1);
        }

        printf("%s\n", ans.c_str());
    }
}