/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 が与えられます。 f_i(S)=T を満たす長さ N の文字列 S と整数 i\ (0\leq i\leq N) の組を 1 つ見つけてください。 そのような 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 を出力してください。
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.