Šeštadieninė informatikos olimpiadininkų mokykla

Duoti du žodžiai. Iš pirmojo žodžio pagal nurodytas taisykles reikia gauti antrą žodį. Keičiama taikant šias operacijas: Perkelti - žymeklis pastumiamas per vieną simbolį į dešinę;

Pašalinti - pašalinamas simbolis, kurį rodo žymeklis; žymeklis rodo tolesnį simbolį;

Pakeisti (x) - simbolis, kurį rodo žymeklis, pakeičiamas simboliu x; žymeklis lieka toje pačioje vietoje;

Įterpti (x) - prieš žymeklio rodomą simbolį įterpiamas simbolis x; žymeklis lieka toje pačioje vietoje;

Numesti - pašalinamas visas žodžio galas, pradedant simboliu, kurį rodo žymeklis (įskaitant ir žymeklio rodomą simbolį); tai gali būti tik paskutinė operacija; žymeklis rodo žodžio pabaigos simbolį.

Pradžioje žymeklis visuomet stovi žodžio pradžioje, ties pirmuoju simboliu. Iš vieno žodžio gauti kitą galima daugeliu būdų. Pavyzdžiui, iš žodžio matai gauti žodį pamatė galime šitaip:

Čia žodį pakeitėme pavartoję 8 operacijas. O gal galima tai padaryti dar greičiau?

Užduotis

Parašykite programą, kuri rastų greičiausią būdą, t. y. mažiausią skaičių operacijų, duotam žodžiui pakeisti kitu duotu žodžiu taikant nurodytas operacijas. Laikoma, kad po paskutiniojo žodžio simbolio eina žodžio pabaigos simbolis. Baigus, žymeklis turi rodyti žodžio pabaigos simbolį, o žymekliui atsistojus ties šiuo simboliu darbas baigiamas.

Pradiniai duomenys

Pradiniai duomenys įrašyti dviejose eilutėse. Pirmoje – pirmasis žodis, antroje – antrasis. Abu žodžiai sudaryti tik iš mažųjų raidžių ir kiekvieno ilgis neviršija 160 simbolių.

Rezultatai

Rezultatą – minimalų operacijų skaičių spausdinkite ekrane.

Pavyzdžiai

mato pamatė

7