問題：AtCoder Beginner Contest 284 F - ABCBAC

解説

公式の解説を見ながらZ-Algorithmで解いた。Z-Algorithmについては参考URLの章の記事を参照してください。

文字列Sを反転した文字列をS'とおき、SとS'をそれぞれ以下のように表現する。

まず、答えが0文字になるようなパターンは以下である。

このときの判定は簡単なので解説は割愛する。

解説の便宜上、以下では答えが1文字以上になるものとする。

答えが1文字以上になるとき、文字列Tは以下のような形をしている。

図の i は文字列のインデックス番号をイメージしている。 $0 \le i \le N-1$ である。

ここで、文字列Tを半分で分割し、文字列half1とhalf2に分ける。Tの長さは2Nなので、half1とhalf2は長さNずつになる。

次に、half2を反転（reverse）したものを新文字列aとし、さらにhalf1とhalf2を入れ替えたものを新文字列bとする。

まず、新文字列aについて考える。

もし文字列Sが見つかるなら、新文字列aの先頭i+1文字と末尾のi+1文字は一致するはずである。この一致するかどうかは、Z-Algorithmを使えばO(1)で判定できる。

新文字列aに対してZ-Algorithmして得た配列をzaとする。すると以下のように文字列Sの存在を 0~i まで判定できる。

次に、新文字列bについて考える。

もし文字列Sが見つかるなら、新文字列bの先頭N-i-1文字と末尾のN-i-1文字は一致するはずである。この一致するかどうかは、Z-Algorithmを使えばO(1)で判定できる。

新文字列bに対してZ-Algorithmして得た配列をzbとする。すると以下のように文字列Sの存在を i+1~N-1 まで判定できる。

2つの判定をパスできたなら、文字列Sは存在することになる。

前処理で使うZ-Algorithmの計算量は $O(N)$ 。

i を 0 ~ N-1 までループして、判定はO(1)でできるので、全体の計算量は $O(N)$ となる。

感想：文字列Tを半分に分割して、反転させたり入れ替えたりするというのが天才解法だと感じた。

Tの長さが2Nなので、「半分に分割する」という発想はわりと典型なのかもしれない。

実装

C++で実装した。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

/**
 * @brief Z-Algorithm
 * 各iについて、S と S.substr(i)の共通接頭辞の長さを格納した配列Zを求める。
 *
 * @tparam T
 * @param S 文字列S
 * @return vector<T> 各iについて共通接頭辞の長さを格納した配列Zを返す。
 */
template <typename T>
vector<T> z_algorithm(string S) {
    T n = S.size();
    vector<T> z(n, 0);
    z[0] = n;

    T i=1, j=0;
    while(i < n) {
        while(i+j<n && S[j]==S[i+j]) j++;
        z[i] = j;

        if (j == 0) {
            i++; continue;
        }

        T k = 1;
        while(k<j && k+z[k]<j) {
            z[i+k] = z[k];
            k++;
        }
        i += k;
        j -= k;
    }

    return z;
}


void solve2() {
    ll N; cin >> N;
    string T; cin >> T;

    string half1 = T.substr(0,N);
    string half2 = T.substr(N,N);
    reverse(half2.begin(), half2.end());

    // 答えが0文字のとき
    if (half1 == half2) {
        cout << T.substr(N,N) << endl;
        cout << 0 << endl;
        return;
    }

    string a = half1 + half2;
    string b = half2 + half1;

    auto za = z_algorithm<ll>(a);
    auto zb = z_algorithm<ll>(b);

    for(ll i=0; i<N; i++) {
        if (za[2*N-(i+1)] == i+1) {
            ll j = N-i-1;
            if (zb[2*N-j] == j) {
                // 答えが見つかった
                cout << a.substr(0,i+1);
                reverse(b.begin(), b.end());
                cout << b.substr(0,j);
                cout << endl;
                cout << i+1 << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
}

int main() {
    // solve();
    solve2();
    return 0;
}