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