Problem G
Beaking spackwards
Languages
da
en
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}](/problems/bakkesnagvendt/file/statement/en/img-0002.png)
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}](/problems/bakkesnagvendt/file/statement/en/img-0003.png)
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 |
