shiftright

ShiftRight

== include(page="template/taskheader" task_id="shiftright") ==

Se dau două şiruri $A$, $B$, de dimensiuni egale, $|A| = |B|$, formate din caractele mici ale alfabetului englez. Pornim de la şirul $A$ şi efectuăm de un număr de ori următoarea operaţie: alegem un subşir (eventual discontiguu), pe care îl **permutăm circular la dreapta** cu o poziţie.

Se dau două 'siruri':https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcR10TmiYExqO0xFJnhfOdmyTS01pCDkPTzFJcz8BMp_OKYpOXUNcw $A$, $B$, de dimensiuni egale, $|A| = |B|$, formate din caractele mici ale alfabetului englez. Pornim de la şirul $A$ şi efectuăm de un număr de ori următoarea operaţie: alegem un subşir (eventual discontiguu), pe care îl **permutăm circular la dreapta** cu o poziţie.

De exemplu, pornind de la şirul $a{**bc**}a{**b**}b{**d**}a$ putem obţine $a{**db**}a{**c**}b{**b**}a$, permutând circular subşirul îngroşat.

Care este numărul minim de operaţii ca să obţinem din şirul $A$ şirul $B$?

Care este numărul minim de operaţii pentru a obţine din şirul $A$ şirul $B$?

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $shiftright.out$ va conţine pe prima linie $ans$, numărul minim de operaţii pentru a ajunge de la şirul $A$ la şirul $B$, iar fiecare dintre următoarele $ans$ linii un număr natural $k$, urmat de $k$ valori între $0$ şi $|A| - 1$, în ordine crescătoare, reprezentând operaţiile, în ordinea efectuării lor. După efectuarea celor $ans$ operaţii, şirurile trebuie să devină egale.

Fişierul de ieşire $shiftright.out$ va conţine pe prima linie $ans$, numărul minim de operaţii pentru a tranforma şirul $A$ în şirul $B$, iar fiecare dintre următoarele $ans$ linii un număr natural $k$, urmat de $k$ valori între $0$ şi $|A| - 1$, în ordine crescătoare, reprezentând operaţiile, în ordinea efectuării lor. După efectuarea celor $ans$ operaţii, şirurile trebuie să devină egale.

Se vor puncta doar soluţiile care afişează cel mult $1.000.000$ (un milion) de poziţii în total. Se garantează că, dacă există soluţie, există măcar o soluţie cu un număr de poziţii totale mai mic sau egal cu $1.000.000$.

h2. Restricţii
* $1 ≤ |A| = |B| ≤ 100.000$

* Orice soluţie corectă se acceptă, cât timp numărul de operaţii este optim, iar la final şirurile devin egale.
* Pentru teste în valoare de **30 de puncte**, se garantează că singurele caractere care apar în cele două şiruri sunt $a$ şi $b$.

* $Orice soluţie corectă se acceptă, cât timp numărul de operaţii este optim, iar la final şirurile devin egale.$
* $Pentru teste în valoare de **30 de puncte**, se garantează că singurele caractere care apar în cele două şiruri sunt $a$ şi $b$.$
* $Şirurile $A$ şi $B$ sunt indexate de la 0.$
* *$Pentru fiecare test, 30% din punctajul lui reprezintă răspunsul afişat corect, în timp ce 70% reprezintă o soluţie validă.$*

h2. Exemplu

h2. Exemple

table(example). |_. shiftright.in |_. shiftright.out |
| abcabbda
  adbacbba
| 1
4 1 2 4 6

|

| abcde
  caebd
| 2
3 0 1 2
3 2 3 4

|

|
| aba
  bab
| -1
|

== include(page="template/taskfooter" task_id="shiftright") ==
 

== include(page="template/taskfooter" task_id="shiftright") ==