Hide

Problem F
Bakke snagvendt

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

Kommunikationsrobotterne KA-1 og Androia elsker at bakke snagvendt: De flytter rundt på forskellige dele af ord og morer sig kosteligt over det fremkomne resultat. Ordet »sodavand« kan fx blive til »vodasand«, og »vaskeklud« til »klaskevud«.

Reglen er, at en streng $x$ er bakket snagvendt af en anden streng $y$, hvis $x$ fremkommer ved at bytte rundt på starten og en anden del af $y$. Helt nøjagtigt skal der gælde, at der findes (muligvis tomme) delstrenge $A$, $B$, $C$ og $D$, således at $x=ABCD$ og $y=CBAD$. I vaskekludseksemplet er $A =\texttt{v}$, $B=\texttt{aske}$, $C=\texttt{kl}$ og $D=\texttt{ud}$:

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

Sommetider går der dog kludder i KA-1s lingvistiske subrutiner og han kommer med nogle nyskabelser, der ikke er rigtigt bakket snagvendt. For eksempel kan han finde på at lave »missetand« om til »massetind«, og det er jo ikke bakket snagvendt. Det er bare vrøvl. Hjælp Androia med hurtigt at opdage den slags løjerligheder.

Her er nogle flere eksempler på at bakke snagvendt:

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

Hverken $x$ eller $y$ behøver at findes i ordbogen.

Indlæsning

To strenge $x$ og $y$ på hver sin linje, af samme længde $n$, med $1 \leq n \leq 250\, 000$. Strengene består af små bogstaver fra a til z.

Udskrift

Et enkelt ciffer, »1« hvis den ene streng er bakket snagvendt af den anden, »0« ellers.

Pointsætning

Der er seks testgrupper. Lad $|s|$ betegne længden af strengen $s$.

Gruppe

Point

Problemstørrelse

Yderligere begrænsninger

1

6

$n\leq 100$

$x$ og $y$ adskiller sig på højst 2 positioner

2

13

$n\leq 250\, 000$

$x$ og $y$ adskiller sig på højst 2 positioner

3

25

$n\leq 5\, 000$

Hvis der er bakket snagvendt, så gælder $|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