Keskustelu: Ohjelmointikysymykset: Python: Kahden merkkijonon pisin yhteinen osa

Terve! Python aloittelija tässä ja tekemässä tällästä tehtävää:

Kirjoita ohjelma, joka etsii kahden merkkijonon pisimmän yhteisen osan
Esimerkiksi jos merkkijonot ovat 'tausta' ja 'muste', pisin yhteinen osa on 'ust'

Olisko mitään esimerkkejä kuinka kirjoittaa tällänen ohjelma?

Kiitos avusta!

Naiivi bruteforce-toteutus olisi käydä ensimmäistä sanaa kirjain kirjaimelta ja kokeilla, löytyisikö toisesta sanasta samaa kirjainta ja kunkin osuman kohdalla laskea myös seuraavat kirjaimet. Sitten tallennetaan paras osumakohta ja paras pituus.

Edellä kuvatusta voi sitten lähteä optimoimaan jos tarvitsee nopeampaa suoritusta, mutta noin pitkillä sanoilla naiivikin toteutus on varmasti riittävä.

Kiitos avusta!

Ongelmanratkaisun perusta on se, että jaetaan ongelma pienempiin osiin. Tämän tehtävän voi hahmottaa palasina ainakin kahdella tavalla:

Tapa 1: Miten pitkä yhteinen osa merkkijonoilla on, kun aloitetaan vertailu jostain tietystä kohdasta? Miten käydään läpi kaikki mahdolliset aloituskohdat kummastakin merkkijonosta?

Tapa 2: Miten käydään läpi kaikki mahdolliset ensimmäisen merkkijonon palaset? Miten selvitetään, sisältyykö kyseinen pala toiseen merkkijonoon?

Pythonissa on myös valmiina kirjasto, jossa on kyseinen algoritmi:

from difflib import SequenceMatcher
string1 = 'Ohjelmointi on kivaa'
string2 = 'Minusta ohjelmointi on toisinaan helppoa, toisinaan vaikeaa'
match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))
print(string1[match.a: match.a + match.size])

Tulostus: hjelmointi on