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])\), thenthere 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\), thenthere 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: