1. naloga
Anagramska razdalja
Dana sta dva niza, s in t, sestavljena le iz malih črk angleške abecede (od a do z). Niz s bi radi predelali tako, da bi iz njega nastal poljuben anagram t-ja, torej poljuben tak niz, ki ga je mogoče dobiti iz t tako, da v njem premešamo vrstni red črk. Pri tem smemo uporabljati naslednje osnovne operacije:
- Dodajanje črke: po eno črko naenkrat lahko vrinemo na enem mestu kjerkoli v nizu, tudi na začetku ali na koncu. Primeri: sol → stol; ali pa tal → stal; ali pa cel → celo.
- Brisanje črke: to je ravno obratna operacija od prejšnje. Kjerkoli v nizu lahko pobrišemo po eno pojavitev ene črke naenkrat; na primer: steze → stez; ali pa steze → teze; ali pa otrok → otok.
- Sprememba črke: po eno pojavitev ene črke lahko spremenimo v poljubno drugo črko; na primer: teta → meta; ali pa teta → trta; ali pa teta → tete.
Napiši podprogram (funkcijo) AnagramskaRazdalja(s, t), ki kot parametra dobi niza s in t in vrne najmanjše število teh osnovnih operacij, s katerim je mogoče iz s dobiti kakšen tak niz, ki je anagram niza t.
Primer: AnagramskaRazdalja("stol", "volt") mora vrniti 1. Z eno operacijo lahko iz stol dobimo vtol, to pa je anagram besede volt.
AnagramskaRazdalja("arbalest", "balasta") mora vrniti 2. Primerno zaporedje dveh operacij (ni pa edino tako) je arbalest → aabalest → aabalst, slednje pa je anagram niza balasta.