Szukam funkcji lub opisu algorytmu poszukującego wzorca w danym pliku. Tj. poszukuje np. ciągu znaków 'abcdef' w plku 'dane.txt'. Chodzi mi o jak najwydajniejszy algorytm, ale za razem prosty w implementacji.
Pozdrawiam
edit : Gdyby ktoś chciał wrzucić tu jakiś kod, to chodzi mi oczywiście o kod w ANSI C.
Najproszta metoda jest sprawdzanie ciagu znak po znaku. [diabel]
Najproszta metoda jest sprawdzanie ciagu znak po znaku. [diabel]
Że też od razu na to nie wpadłem [glowa], może dlatego, że to zbyt proste :-P Ma ktoś jeszcze jakieś propozycje ?
Powyższa metoda jest najprostrza, ale nie najszybsza. W FAQ/Gotowcach/Artykuach są opisane o wiele szybsze algorytmy.
Chciałem podać link, ale wyszukiwarka na głównej stronie nie działa.
Polecam ten najprostszy algorytm jesli nie potrzebne Ci bardziej uogolnione wzorce. Jest najprostszy a istniejace szybsze są conajwyzej troche szybsze a nie o wiele. Są przy tym dużo bardziej skomplikowane. Ten algorytm ma w prawdzie zlozonosc obliczeniowa rzedu n^2, jednak w praktyce sredni koszt jest liniowy, wiec nic o wiele szybszego nie ma i byc nie moze.
Ten algorytm ma w prawdzie zlozonosc obliczeniowa rzedu n^2
n^2? jakim cudem, skoro wzorzec, z którym porównujesz, ma 1 bajt? pozostałe bajty sprawdza się tylko, gdy pasują poprzednie. statystycznie rzecz biorąc, algorytm jest klasy n*log(n), przy czym logarytm ma podstawę nie dwa, a coś koło 128.
sorki co to jest moc obliczeniowa argorytmu ????? jak ja sprawdzić ???
sorki co to jest moc obliczeniowa argorytmu ????? jak ja sprawdzić ???
Czas działania algorytmu w zależności od ilości danych, które musi obrobić (najczęściej są to zależności logN, N, NlogN i N^2).