Toimintosarja SIMILAR_TEXT

Toimintosarja SIMILAR_TEXT laskee kahden merkkijonon samankaltaisuuden.

Kahden merkkijonon samankaltaisuuden laskeminen tapahtuu Programming Classics: Implementing the World's Best Algorithms by Oliver (ISBN 0-131-00413-1) kuvatulla menetelmällä. Huomaa, että tämä toteutus ei käytä pinoa kuten Olivers pseudokoodissa, mutta se käyttää rekursiivisia kutsuja, jotka voivat parantaa suorituskykyä (mutta eivät välttämättä). Huomaa myös, että tämän algoritmin monimutkaisuus on O(N³), jossa N on pisimmän merkkijonon pituus.

Syöte STR1

Syöte määrittää ensimmäisen verrattavan merkkijonon.

Syöte STR2

Syöte määrittää toisen verrattavan merkkijonon.

Tulo SIM

Tulo palauttaa molempien merkkijonojen yhteneväisten merkkien määrän.

Yhteneväisten merkkien määrä lasketaan etsimällä pisin yhteinen alkumerkkijono ja toistamalla tämä rekursiivisesti prefiksille ja suffiksille. Kaikkien löydettyjen yhteisten osamerkkijonojen pituudet summataan.

Tulo PERCENT

Tulo palauttaa samankaltaisuuden prosenttimääränä liukulukuna. Tämän laskemiseksi tulos jaetaan annettujen merkkijonojen pituuksien keskiarvolla ja kerrotaan sadalla.