Score : $500$ points

问题描述

对于一个长度为 $N$ 的字符串 $S$ 和一个整数 $i\ (0\leq i\leq N)$，我们定义字符串 $f_i(S)$ 如下：

• 字符串 $S$ 的前 $i$ 个字符，
• 字符串 $S$ 的反转，
• 字符串 $S$ 的最后 $(N-i)$ 个字符，

按照这个顺序拼接而成。例如，如果 $S=$ abc 并且 $i=2$，那么有 $f_i(S)=$ abcbac。

现给定一个长度为 $2N$ 的字符串 $T$。找出一对字符串 $S$（长度为 $N$）和整数 $i\ (0\leq i\leq N)$，使得 $f_i(S)=T$。若不存在这样的字符串 $S$ 和整数 $i$ 的组合，请报告这一事实。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For a string $S$ of length $N$ and an integer $i\ (0\leq i\leq N)$, let us define the string $f_i(S)$ as the concatenation of:

• the first $i$ characters of $S$,
• the reversal of $S$, and
• the last $(N-i)$ characters of $S$,

in this order. For instance, if $S=$ abc and $i=2$, we have $f_i(S)=$ abcbac.

You are given a string $T$ of length $2N$. Find a pair of a string $S$ of length $N$ and an integer $i\ (0\leq i\leq N)$ such that $f_i(S)=T$. If no such pair of $S$ and $i$ exists, report that fact.

Constraints

• $1\leq N \leq 10^6$
• $N$ is an integer.
• $T$ is a string of length $2N$ consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$

$T$

Output

If no pair of $S$ and $i$ satisfies the condition, print -1. Otherwise, print $S$ and $i$, separated by a newline. If multiple pairs of $S$ and $i$ satisfy the condition, you may print any of them.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if $S=$ abc and $i=2$, we have $f_i(S)=$ abcbac, which equals $T$, so you should print abc and $2$.

Sample Input 2

4
abababab

Sample Output 2

abab
1

$S=$ abab and $i=3$ also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

$S=$ agc and $i=3$ also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of $S$ and $i$ satisfies the condition, print -1.

update @ 2024/3/10 11:54:13