Fişierul intrare/ieşire:	shiftright.in, shiftright.out	Sursă	FMI No Stress 8
Autor	Lucian Bicsi	Adăugată de	Fmi no stress 2018 •fminostress2018
Timp execuţie pe test	1 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

ShiftRight

Se dau două siruri 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 abcabbda putem obţine adbacbba, permutând circular subşirul îngroşat.

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

Date de intrare

Fişierul de intrare shiftright.in conţine pe prima linie şirul A, iar pe a doua linie şirul B.

Date de ieşire

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.

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.
• Ş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ă.

Exemple

Cum se trimit solutii?