算法

(Z算法) $O(N)$

前置知识：见 字符串问题笔记

$Z$ 算法可以在 $O(N)$ 时间内求出 $S$ 和 $S$ 从 $i$ 开始的后缀 S[i:] 的最长公共前缀

一些记号：

rev(T)：对 $T$ 做翻转
T[l:r]：$T$ 的从第 $l$ 个字符到第 $r-1$ 个字符构成的子串
Z(T)[i]：$T$ 和 T[i:] 的 $\operatorname{lcp}$ 的长度。为了方便，令 Z(T)[|T|] = 0

我们可以先对题目条件进行转化，以下四种情况是等价的：

• 存在 $i(0 \leqslant i \leqslant N)$，使得 $f_i(S) = T$ (下文的 $i$ 默认范围都是 $[0, N]$)
• 存在 $i$ 使得 T[0:i] = rev(T[N:N+i]) 并且 T[N+i:2N] = rev(T[i:N])
  记 A = T[0, N]，B = rev(T[N, 2N])
• 存在 $i$ 使得 A[0:i] = B[N-i:N] 并且 A[i:N] = B[0:N-i]
  记 X=A+B，Y=B+A
• 存在 $i$ 使得 Z(X)[2N-i] = i 并且 Z(Y)[N+i] = N-i

最后一种情况可以通过预处理 $Z(X)$ 和 $Z(Y)$ 然后 $O(1)$ 判定。

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    string t;
    cin >> n >> t;

    string s = t.substr(0, n);
    t = t.substr(n);
    reverse(t.begin(), t.end());

    string a = s+t;
    string b = t+s;
    auto za = z_algorithm(a);
    auto zb = z_algorithm(b);

    rep(i, n) {
        if (i and za[n*2-i] != i) continue;
        int j = n-i;
        if (zb[n*2-j] != j) continue;
        string ans = s.substr(0, i);
        reverse(s.begin(), s.end());
        ans += s.substr(0, j);
        cout << ans << '\n' << i << '\n';
        return 0;
    }

    puts("-1");

    return 0;
}