Hide

Problem G
Beaking spackwards

/problems/bakkesnagvendt/file/statement/en/img-0001.png

The Danish communication robots KA-1 and Androia love beaking spackwards: They switch parts of words and are endlessly amused by the results. For instance, the word “sodavand” becomes “vodasand” and “vaskeklud” becomes “klaskevud.”

The rule is that string $x$ is said to be boken spackwards of string $y$ if $x$ results from exchanging the start of $y$ with another part of $y$. To be precise, there must be (possibly empty) substrings $A$, $B$, $C$, and $D$ such that $x=ABCD$ and $y=CBAD$. For instance, “vaskeklud” is boken spackwards of “klaskevud” with $A =\texttt{v}$, $B=\texttt{aske}$, $C=\texttt{kl}$ and $D=\texttt{ud}$:

\includegraphics[width=0.2\textwidth ]{img/ex-vaskeklud.pdf}

Sometimes, KA-1’s linguistic subroutines are buggy and he comes up with constructions that aren’t properly boken spackwards. For instance, he might transform “missetand” to “massetind,” which isn’t boken spackwards at all. It’s just balderdash. Help Androia quickly discover this kind of gibberish.

Here are some more examples of beaking spackwards:

\includegraphics[width=0.8\textwidth ]{img/ex-other.pdf}

Neither $x$ nor $y$ need to be words in the dictionary.

Input

Two strings $x$ and $y$ on separate lines, each of length $n$ with $1 \leq n \leq 250\, 000$. The strings consist of lower case letters from a to z.

Output

A single digit, “1” if one string is boken spackwards of the other, “0” otherwise.

Points

There are six test groups. Let $|s|$ denote the length of string $s$.

Groups

Points

Problem size

Additional constraints

1

6

$n\leq 100$

$x$ and $y$ differ in at most $2$ positions

2

13

$n\leq 250\, 000$

$x$ and $y$ differ in at most $2$ positions

3

25

$n\leq 5\, 000$

If $x$ and $y$ are boken spackwards, then with $|A|=|C|$

4

26

$n\leq 10$

5

27

$n\leq 5\, 000$

6

3

$n\leq 250\, 000$

Sample Input 1 Sample Output 1
sodavand
vodasand
1
Sample Input 2 Sample Output 2
vaskeklud
klaskevud
1
Sample Input 3 Sample Output 3
missetand
massetind
0
Sample Input 4 Sample Output 4
ac
ca
1
Sample Input 5 Sample Output 5
erstatte
attester
1
Sample Input 6 Sample Output 6
biksemad
biksemad
1
Sample Input 7 Sample Output 7
baksemad
biksemad
0
Sample Input 8 Sample Output 8
bcbcbbcd
dcbbcbcb
1

Please log in to submit a solution to this problem

Log in