この問題は様々な文字列アルゴリズムによって解くことができますが、本解説では、AtCoder Library にも実装されている Z algorithm を用いた解法を説明します。

以下、文字列は 0-indexed で扱います（すなわち、先頭を \(0\) 文字目とします）。

Z algorithm とは

文字列 \(S\) が与えられる。\(S\) の \(i\) 文字目以降のみを取り出した文字列を \(S[i:]\) とおく。\(0\) 以上 \(|S|\) 未満の全ての \(i\) に対して、\(S\) と \(S[i:]\) の最大共通接頭辞の長さ (\(S\) と \(S[i:]\) が先頭から何文字一致しているか) を求めよ。

Z algorithm は、上の問題を \(O(|S|)\) で解くアルゴリズムです。アルゴリズムの詳細についてはAtCoder Library の実装やすぬけさんによる解説などをご参照ください。

本問題の解法

以下、文字列 \(S\) に対して、

• \(S\) を反転させた文字列を \(\mathrm{rev}(S)\) と表記します。
• \(S\) の \(l\) 文字目から \(r-1\) 文字目までの部分文字列 (\(l=r\) の場合は空文字列) を \(S[l:r]\) と表記します。
• \(S\) と \(S[i:]\) の最大共通接頭辞の長さを \(Z(S)[i]\) と表記します。また、便宜上 \(Z(S)[|S|]=0\) とします。

まずは問題文の条件を言い換えます。以下の \(4\) つの条件は全て同値です (証明は簡単です)。

• ある \(S,i\ (0\leq i \leq N)\) が存在して、\(f_i(S)=T\)

• ある \(i\ (0\leq i \leq N)\) が存在して、\(T[0:i]=\mathrm{rev}(T[N:N+i])\) かつ \(T[N+i:2N]=\mathrm{rev}(T[i:N])\)
  
  \(A=T[0:N],B=\mathrm{rev}(T[N:2N])\) とおいたとき、

• ある \(i\ (0\leq i \leq N)\) が存在して、\(A[0:i]=B[N-i:N]\) かつ \(A[i:N]=B[0:N-i]\)
  
  \(A\) と \(B\) をこの順に連結した文字列を \(X\)、 \(B\) と \(A\) をこの順に連結した文字列を \(Y\) とおいたとき、

• ある \(i\ (0\leq i \leq N)\) が存在して、\(Z(X)[2N-i]=i\) かつ \(Z(Y)[N+i]=N-i\)

最後の条件は、\(X\) と \(Y\) に対して Z algorithm を用いて \(Z(X)\) と \(Z(Y)\) を予め求めておくことによって、各 \(i\) に対して \(O(1)\) で判定できます。よって、この問題を \(O(N)\) で解くことができました。

なお、冒頭に述べた通り、rolling hash、suffix array、MP などのその他の文字列アルゴリズムを用いることによっても、\(O(N)\) でこの問題を解くことができます。rolling hash を用いる場合は hash 値の衝突に注意してください。

実装例 (C++) :

#include<bits/stdc++.h>
#include<atcoder/string>

using namespace std;
using namespace atcoder;

int main() {
    int n;
    cin >> n;
    string t;
    cin >> t;
    
    string a = t.substr(0, n);
    string b = t.substr(n);
    reverse(b.begin(), b.end());
    
    string x = a + b;
    vector<int> za_x = z_algorithm(x);
    za_x.push_back(0);
    
    string y = b + a;
    vector<int> za_y = z_algorithm(y);
    za_y.push_back(0);
    
    for (int i = 0; i <= n; i++) {
        if(za_x[2 * n - i] < i) continue;
        if(za_y[n + i] < n - i) continue;
        cout << t.substr(0, i) + t.substr(n + i) << endl;
        cout << i << endl;
        return 0;
    }
    
    cout << -1 << endl;
}