Ion este un lingvist pasionat. Recent el a descoperit un text scris intr-o limba necunoscuta. Textul este scris pe mai multe linii si este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spatii sau/si semne de punctuatie $(,:;.!?-)$.
Ion a fost frapat ca exista multe similitudini intre cuvintele din text. Fiind foarte riguros, Ion defineste similitudinea a doua cuvinte dupa cum urmeaza.

Fie c<sub>1</sub> si c<sub>2</sub> doua cuvinte. Cuvantul c<sub>1</sub> poate fi obtinut din cuvantul c<sub>2</sub> printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:

Fie $c1$ si $c2$ doua cuvinte. Cuvantul $c1$ poate fi obtinut din cuvantul $c2$> printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:

| Operatia
| Efect
| Exemplu
|

| $move(c<sub>1</sub>,c<sub>2</sub>)$
| Muta primul caracter din $c<sub>1</sub>$ la sfarsitul cuvantului $c<sub>2</sub>$
| Daca $c<sub>1</sub>="alba"$ si $c<sub>2</sub>="neagra"$, dupa efectuarea operatiei $move(c<sub>1</sub>, c<sub>2</sub>)$, $c<sub>1</sub>$ va fi $"lba"$, iar $c<sub>2</sub>$ va fi $"neagraa"$.

| $move(c1,c2)$
| Muta primul caracter din $c1$ la sfarsitul cuvantului $c2$
| Daca $c1="alba"$ si $c2="neagra"$, dupa efectuarea operatiei $move(c1, c2)$, $c1$ va fi $"lba"$, iar $c2$ va fi $"neagraa"$.

|

| $insert(c<sub>1</sub>,x)$
| Insereaza caracterul $x$ la inceputul lui $c<sub>1</sub>$
| Daca $c<sub>1</sub>="alba"$ si $x='b'$, dupa executarea operatiei $insert(c<sub>1</sub>,x)$, $c<sub>1</sub>$ va fi $"balba"$.

| $insert(c1,x)$
| Insereaza caracterul $x$ la inceputul lui $c1$
| Daca $c1="alba"$ si $x='b'$, dupa executarea operatiei $insert(c1,x)$, $c1$ va fi $"balba"$.

|

| $delete(c<sub>1</sub>)$
| Sterge primul caracter din $c<sub>1</sub>$
| Daca $c<sub>1</sub>="alba"$, dupa executarea operatiei $delete(c<sub>1</sub>)$, $c<sub>1</sub>$ va fi $"lba"$.

| $delete(c1)$
| Sterge primul caracter din $c1$
| Daca $c1="alba"$, dupa executarea operatiei $delete(c1)$, $c1$ va fi $"lba"$.

|

Definim similitudinea dintre $c<sub>1</sub>$ si $c<sub>2</sub>$ ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c<sub>1</sub>$ in cuvantul $c<sub>2</sub>$ (operatiile $move$ nu se numara).
Fie $c<sub>0</sub>$ primul cuvant din text. Incepand cu $c<sub>0</sub>$ putem construi lanturi de $k-similitudine$.

Definim similitudinea dintre $c1$ si $c2$ ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c1$ in cuvantul $c2$ (operatiile $move$ nu se numara).
Fie $c0$ primul cuvant din text. Incepand cu $c0$ putem construi lanturi de $k-similitudine$.

Un lant de $k-similitudine$ este o succesiune de cuvinte distincte din text cu urmatoarele proprietati:
* daca cuvantul $x$ apare in lant inaintea cuvantului $y$, atunci prima aparitie a lui $x$ in text preceda prima aparitie a lui $y$ in text;