300623: CF119D. String Transformation

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

Description

String Transformation

题意翻译

我们先定义这么一个函数$R(X)$,表示把$X$这个字符串翻转,比如: $R(\texttt{'ASD'})=\texttt{'DSA'}$; $R(\texttt{'aaa'})=\texttt{'aaa'}$; 再定义函数$F(s,i,j)$,其中$F$的自变量$s$为字符串,$i$、$j$为$0$到$N-1$的整数,$i < j$,满足: $F(s,i,j)=s[i+1\ldots j-1]+R(s[j\ldots n-1])+R(s[0\ldots i])$ $+$即为字符串首尾相接,这个字符串下标为$0\sim n-1$,$s[i\ldots j]$表示从下标$i$到下标$j$的子串。 现在我们有两个字符串$A$、$B$,要求出$i$、$j$,满足$F(A,i,j)=B$; 如果没有这样的$i$,$j$,输出`-1 -1`; 如果有多组解,求$i$最大的,如果$i$仍然相同,求$j$最小的。 输入可能包含稀奇古怪的字符。

题目描述

Let $ s $ be a string whose length equals $ n $ . Its characters are numbered from 0 to $ n-1 $ , $ i $ and $ j $ are integers, $ 0<=i&lt;j&lt;n $ . Let's define function $ f $ as follows: $ f(s,i,j)=s[i+1...\ j-1]+r(s[j...\ n-1])+r(s[0...\ i]) $ . Here $ s[p...\ q] $ is a substring of string $ s $ , that starts in position $ p $ and ends in position $ q $ (inclusive); "+" is the string concatenation operator; $ r(x) $ is a string resulting from writing the characters of the $ x $ string in the reverse order. If $ j=i+1 $ , then the substring $ s[i+1...\ j-1] $ is considered empty. You are given two strings $ a $ and $ b $ . Find such values of $ i $ and $ j $ , that $ f(a,i,j)=b $ . Number $ i $ should be maximally possible. If for this $ i $ there exists several valid values of $ j $ , choose the minimal $ j $ .

输入输出格式

输入格式


The first two input lines are non-empty strings $ a $ and $ b $ correspondingly. Each string's length does not exceed $ 10^{6} $ characters. The strings can contain any characters with ASCII codes from 32 to 126 inclusive.

输出格式


Print two integers $ i $ , $ j $ — the answer to the problem. If no solution exists, print "-1 -1" (without the quotes).

输入输出样例

输入样例 #1

Die Polizei untersucht eine Straftat im IT-Bereich.
untersucht eine Straftat.hciereB-TI mi  ieziloP eiD

输出样例 #1

11 36

输入样例 #2

cbaaaa
aaaabc

输出样例 #2

4 5

输入样例 #3

123342
3324212

输出样例 #3

-1 -1

Input

题意翻译

我们先定义这么一个函数$R(X)$,表示把$X$这个字符串翻转,比如: $R(\texttt{'ASD'})=\texttt{'DSA'}$; $R(\texttt{'aaa'})=\texttt{'aaa'}$; 再定义函数$F(s,i,j)$,其中$F$的自变量$s$为字符串,$i$、$j$为$0$到$N-1$的整数,$i < j$,满足: $F(s,i,j)=s[i+1\ldots j-1]+R(s[j\ldots n-1])+R(s[0\ldots i])$ $+$即为字符串首尾相接,这个字符串下标为$0\sim n-1$,$s[i\ldots j]$表示从下标$i$到下标$j$的子串。 现在我们有两个字符串$A$、$B$,要求出$i$、$j$,满足$F(A,i,j)=B$; 如果没有这样的$i$,$j$,输出`-1 -1`; 如果有多组解,求$i$最大的,如果$i$仍然相同,求$j$最小的。 输入可能包含稀奇古怪的字符。

加入题单

上一题 下一题 算法标签: