Official

F - ABCBAC Editorial by en_translator


This problem can be solved with various string algorithms. In this editorial, we adopt the Z algorithm, which is included in AtCoder Library.

In this article, we adopt zero-based indexing for a string (that is, the initial character is considered the “\(0\)-th” one).

What is Z algorithm?


You are given a string \(S\). Let \(S[i:]\) be the string consisting of the \(i\)-th and subsequent characters. For each \(i\) between \(0\) (inclusive) and \(|S|\) (exclusive), find the length of the longest common prefix of \(S\) and \(S[i:]\) (how many initial characters of \(S\) and \(S[i:]\) coincides).


The Z algorithm solves the problem above in an \(O(|S|)\) time. For more details, please refer to the Implementation in AtCoder Library and article by snuke (in Japanese).

Solution for this problem

Let us define some notations:

  • let \(\mathrm{rev}(S)\) be the reversal of \(S\);
  • let \(S[l:r]\) be the substring of \(S\) from the \(l\)-th through \((r-1)\)-th characters (or an empty string if \(l=r\));
  • let \(Z(S)[i]\) be the length of the longest common prefix of \(S\) and \(S[i:]\). For convenience, let \(Z(S)[|S|]=0\).

We first rephrase the condition in the Problem Statement. The following four conditions are equivalent (the proof is easy).

  • There exist \(S\) and \(i\ (0\leq i \leq N)\) such that \(f_i(S)=T\)

  • There exists \(i\ (0\leq i \leq N)\) such that \(S[0:i]=\mathrm{rev}(S[N:N+i])\) and \(S[N+i:2N]=\mathrm{rev}(S[i:N])\).

    Let \(A=S[0:N]\) and \(B=\mathrm{rev}(S[N:2N])\), then

  • there exists \(i\ (0\leq i \leq N)\) such that \(A[0:i]=B[N-i:N]\) and \(A[i:N]=B[0:N-i]\).

    Let \(X\) be the concatenation of \(A\) and \(B\) in this order, and \(Y\) be that of \(B\) and \(A\), then

  • there exists \(i\ (0\leq i \leq N)\) such that \(Z(X)[2N-i]=i\) and \(Z(Y)[N+i]=N-i\).

The last condition can be determined in an \(O(1)\) for each \(i\) by precalculating \(Z(X)\) and \(Z(Y)\) against \(X\) and \(Y\). Thus, the problem has been solved in a total of \(O(N)\) time.

As mentioned initially, note that one can use other algorithms in a total of \(O(N)\) time using rolling hash, suffix array, or MP (Morris–Pratt algorithm). Beware of hash value collision if you use rolling hash.

Sample code (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;
}

posted:
last update: