102845: [AtCoder]ABC284 F - ABCBAC

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

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.

Input

题意翻译

对于一个长度为 $N$ 的字符串 $S$ 和一个整数 $i\in [0,N]$,定义 $f_i(S)$ 所得的字符串为以下三者顺次连接: - $S$ 的前 $i$ 个字符; - 将 $S$ 翻转得到的字符串; - $S$ 的后 $N-i$ 个字符。 例如,对于 $S=\texttt{abc}$,$i=2$ 有 $f_i(S)=\texttt{abcbac}$。 现在有一个长度为 $2N$ 的字符串 $T$,你需要求出任意一对 $(S,i)$ 满足 $f_i(S)=T$。如果不存在,输出 $-1$。 翻译 by @Mars\_Dingdang

Output

分数:500分

问题描述

对于长度为$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$。找出一个长度为$N$的字符串$S$和一个整数$i\ (0\leq i\leq N)$,使得$f_i(S)=T$。如果不存在这样的$S$和$i$,报告这个事实。

约束

  • $1\leq N \leq 10^6$
  • $N$是一个整数。
  • $T$是一个长度为$2N$的由小写英文字母组成的字符串。

输入

输入通过标准输入给出以下格式:

$N$ 
$T$

输出

如果不存在满足条件的$S$和$i$,打印-1。否则,以换行符分隔的方式打印$S$和$i$。如果有多个满足条件的$S$和$i$,你可以打印其中任意一对。


样例输入1

3
abcbac

样例输出1

abc
2

如问题描述中提到的,如果$S=$ abc 和 $i=2$,我们有$f_i(S)=$ abcbac,等于$T$,所以你应该打印abc和$2$。


样例输入2

4
abababab

样例输出2

abab
1

$S=$ abab 和 $i=3$ 也满足条件。


样例输入3

3
agccga

样例输出3

cga
0

$S=$ agc 和 $i=3$ 也满足条件。


样例输入4

4
atcodeer

样例输出4

-1

如果不存在满足条件的$S$和$i$,打印-1

加入题单

上一题 下一题 算法标签: