分数: 500 点
问题陈述
对于字符串 S 长度 N 和一个整数 i\ (0\leq i\leq N),让我们定义字符串 f_i(S) 作为以下内容的串联:
- 第一 i 的字符 S,
- 逆转 S,和
- 最后 (N-i) 的字符 S,
按此顺序。
例如,如果 S= abc 和 i=2,我们有 f_i(S)= abcbac.
给你一个字符串 T 长度 2N。 找到一对字符串 S 长度 N 和一个整数 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.