[algorytm] porównywanie plików

Poszukuję sposobu porównania dwóch stringów. Czy znacie jakieś algorytmy, które mógłbym przeanalizować? Chciałbym napisać program, który weźmie dwa stringi i zwróci tablicę z częściami wspólnymi. Z tym, że:

string1 = ala ma kota
string2 = ala ma psa

powinno zwrócić:

ala ma

Natomiast:

string1 = ala ma kota i lubi frytyki
string2 = ala ma psa i lubi frytyki

powinno zwrócić:

ala ma
i lubi frytyki

Pytanie czy da się to rozszerzyć i jak o bardziej rozbudowane przykłady jak np. porównywanie plików html

string1 = <strong>lubię pakować</strong>
string2 = <strong>strongman</strong>

powinno zwrócić:

<strong>
</strong>

Jak tego dokonać, bo kombinuję na różne sposoby, ale nic sensownego mi nie wychodzi. Nie chciałbym ograniczać się do jednego typu danych, tj. stworzenia np. parsera HTML - chciałbym, aby program porównywał stringi tak jak porównują je ludzie.

poczytaj kod biblioteki difflib do pythona - python jest bardzo przystępny dla początkujących, więc raczej nie powinieneś mieć problemów z czytaniem języka, którego i tak warto znać.

Chciałem w desperacji poczytać o unixowym [b]diff[/b], jednak mam nadzieję, że może ktoś wcześniej podrzuci link do jakiegoś źródła z algorytmem lub czymś pomocnym. Tak czy inaczej dzięki.

diff to program pisany w C, a jak wszyscy wiemy, C nie jest językiem, w którym przetwarzanie ciągów znaków jest najwygodniejsze. tak jak mówiłem, poszukaj w codesearch.google.com kodu difflib, albo po prostu ściągnij paczkę z sourcem pythona

http://docs.python.org/library/difflib.html#module-difflib <- jak używać

http://svn.python.org/view/python/trunk/Lib/difflib.py?rev=65617&view=markup <- źródła

Miłej lektury.

Dzięki za pomoc :)

for i = 1to dlugosc tekstu rób
if s1[i] != s2[i] break;
return nie wiem s1.delete(1,i);

// [glowa] - deus