Šeštadieninė informatikos olimpiadininkų mokykla

Atliekant elementarius veiksmus iš vieno žodžio galima gauti kitą. Šiame uždavinyje nagrinėsime vieno žodžio transformavimą į kitą, naudojant tris veiksmus:

Pakeitimą: vieną žodžio raidę galima pakeisti kita, pavyzdžiui akis -> avis. Ištrynimą: vieną žodžio raidę galima ištrinti, pavyzdžiui, narvas -> naras. Įterpimą: į žodį galima įterpti raidę, pavyzdžiui, takas -> tankas. Duoti du žodžiai. Parašykite programą, kuri išspausdintų, kokius elementarius pakeitimus iš išvardintų reikia atlikti, norint iš pirmojo žodžio gauti antrąjį. Pakeitimų skaičius turi būti minimalus.

Pradiniai duomenys

Pradinių duomenų failo pirmose dviejose eilutėse įrašyti žodžiai, sudaryti iš mažųjų lotyniškų raidžių. Žodžiai neilgesni negu 100 simbolių.

Rezultatai

Į rezultatų failo pirmą eilutę turi būti įrašytas minimalus elementarių pakeitimų, reikalingų iš pirmojo žodžio gauti antram, skaičius K. Sekančiose K eilučių turi būti išvardinti patys pakeitimai. Šių pakeitimų formatas laisvas, tačiau veiksmai turi būti numeruojami, turi būti aišku, su kokiais simboliais atliekamas veiksmas. Pati veiksmų tvarka nesvarbi.

(Sistema patikrins tik veiksmų skaičiaus teisingumą, tačiau nepatingėkit užprogramuoti ir veiksmų išvedimą - tame visas įdomumas:)

Pavyzdžiai

linksma
keista

5
1) pakeisti "m" į "t" (poz. 6)
2) ištrinti "k" (poz. 4)
3) ištrinti "n" (poz. 3)
4) įterpti "e" (poz. 1)
5) pakeisti "l" į "k" (poz. 1)