4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Levenshtein

Odległość Levenshteina to miara odmienności napisów. Dwa identyczne napisy dzieli odległość 0. Dwa nieidentyczne napisy dzieli odległość równa liczbie elementarnych operacji (dodaj znak, usuń znak, zamień znak), które należy wykonać na dowolnym z napisów, aby w efekcie otrzymać drugi.

Poniżej przedstawiamy jeden z możliwych algorytmów obliczenia odległości Levenshteina (źródło)

• stwórz tablicę dwuwymiarowę o wymiarach n+1 x m+1, gdzie n i m to odpowiednio długości porównywanych słów
• pierwszy wiersz i pierwszą kolumnę wypełnij wartościami od 0 do odpowiednio n i m
• weź po kolei wartości wierszy i porównuj literę dotyczącą tego wiersza z literą dotyczącą kolejnych kolumn
• przy każdym porównaniu wykonaj poniższą procedurę:
  • jeśli litery są identyczne, ustaw koszt na 0, jeśli nie, na 1
  • wypełnij daną komórkę wartością, którą będzie minimum z:
    • wartości komórki leżącej bezpośrednio nad naszą aktualną komórka zwiększoną o 1
    • wartości komórki leżącej bezpośrednio w lewo od naszej aktualnej komórki zwiększoną o 1
    • wartości komórki leżącej bezpośrednio w lewą-górna stronę od aktualnej komórki powiększoną o koszt
• po wykonaniu wszystkich porównań, prawa dolna komórka tablicy będzie zawierać obliczoną odległość Levenshteina
  

Twoim zadaniem będzie posortowanie zbioru słów według odległości Levenshteina względem pewnego słowa bazowego.

Wejś›cie

Kolejno:

• wiersz zawierający słowo bazowe
• wiersz zawierający liczbę słów w sortowanym zbiorze (n - liczba naturalna nie większa od 100)
• n wierszy zawierających po jednym słowie z sortowanego zbioru

Wyjś›cie

• n wierszy zawierających sortowane słowo oraz po spacji jego odległość względem słowa bazowego
• w przypadku słów o takiej samej odległości, wyprowadź je w takiej kolejności w jakiej znajdowały się na wejściu

Przykł‚ad

Wejś›cie: 

foka
5
kotka
foka
pies
fretka
rybka

Wyjście:

foka 0
kotka 2
fretka 3
rybka 3
pies 4

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 4,0