W dniu poniedziałek, 7 stycznia 2013 17:44:25 UTC+1 użytkownik identyfikator:
20040501 napisał:
> zna Ktoś może jakiś cwany, to znaczy prosty algorytm wyszukiwania ciągu w
> ciągu?
Jakoś to się robiło taką sumę, którą można obliczać "przyrostowo", i jak
suma dla wzorca i podciągu była taka sama, to dopiero wtedy porównywało się
znak po znaku - szczegółów nie pamiętam w tej chwili. Im "lepiej" policzymy
sumę, tym mniej porównań znak po znaku. To po pierwsze.

Po drugie, być może potrzebujesz wiele razy wyszukiwać różny wzorzec w
tym samym tekście - wtedy warto zastanowić się nad jakimś zahashowaniem
par (suma,pozycja w tekscie).

Po trzecie, być może tekst w którym wyszukujesz, czasami się zmienia - wtedy
warto pomyśleć o jakimś zahashowaniu które da się modyfikować.

Gdy tekst nie mieści się cały w RAM i jest na dysku - to następna wariacja
na temat. Gdy tekst jest na wielu dyskach w rozproszonym środowisku
komputerów - następna wariacja. Gdy tekst jest na taśmie a nie na dysku
z ruchomą głowicą - jeszcze inna wariacja. Gdy tekst jest w bazie danych, a
baza danych udostępnia gotowe narzędzia - jeszcze inna sprawa.

Kiedyś pisałem programik do gry w odmianę scrabli, tam z kolei było wiele
wzorców (powiedzmy że średnio 100 wzorców) i wiele tekstów do przeszukania -
te teksty to pojedyncze słowa z języka polskiego. Czyli dochodzimy do ciągu
ze znakiem uniwersalnym (który pasuje do dowolnego znaku) i przeszukiwania
milionów króciutkich tekstów...

A niby to tylko wyszukiwanie tekstu w tekście....

Pozdrawiam