Ten wpis pochodzi z naszego linkbloga *ptr, dlatego nie widać go na głównej. *ptr możesz czytać przez RSS albo przez sidebar po prawej stronie serwisu.
Trochę nieoptymalne to szukanie, po prostu 256 razy szuka xorując sobie bufor za każdym razem inną stałą. A wystarczyłoby wyliczyć stałą xorującą na podstawie kolejnych znaków z pliku xorując je z pierwszym znakiem szukanego stringu (pierwszy znak dla tej stałej już się będzie zgadzał).
A jeszcze lepiej: zrobić xor sąsiednich znaków w pliku i szukanym tekście, wtedy można użyć dowolnego algorytmu szukania (np. użytego tam KMP). Oczywiście raz zamiast 256 razy.
A bajkę o Tymitumie znam, tylko jakoś nie widzę zastosowania ;)
Może zbyt skrótowo to wytłumaczyłem. Lepiej na przykładzie. Dla uproszczenia binarnie.
Plik: 10101001010101001001
Szukany string: 11011
Metoda 1:
Wiemy że szukany string zaczyna się od 1, więc stała xorująca na pierwszej pozycji pliku musi być 0 żeby szukany string mógł się tam znaleźć (bo w pliku jest tam też 1), dla drugiej pozycji pliku stała xorująca = 1 (bo w pliku jest 0) itd. Ogólnie stała xorująca = pierwszy znak szukanego stringu xor znak z pliku gdzie akurat spodziewamy się tego znaku.
Metoda 2:
Xorujemy sąsiednie znaki w pliku i szukanym stringu (skraca nam to oba o 1 znak):
Plik: 10101001010101001001 => 1111101111111101101
Szukany string: 11011 => 0110
no i “od razu widać” (znaczy się: używamy dowolnej metody szukania) że szukany string występuje pod koniec.
Dowód poprawności obu metod pozostawiam czytelnikowi :)
Posłuchaj jednego z naszych 8 cyberwykładów. Wiedzę podajemy z humorem i w przystępny dla każdego pracownika sposób. Zdalnie lub u Ciebie w firmie. Kliknij tu i zobacz opisy wykładów!
Każdy powinien zobaczyć te webinary! Praktyczna wiedza i zrozumiały język. 6 topowych tematów — kliknij tutaj i zobacz szczegółowe opisy oraz darmowy webinar.
Posłuchaj jednego z naszych 8 cyberwykładów. Wiedzę podajemy z humorem i w przystępny dla każdego pracownika sposób. Zdalnie lub u Ciebie w firmie. Kliknij tu i zobacz opisy wykładów!
Każdy powinien zobaczyć te webinary! Praktyczna wiedza i zrozumiały język. 6 topowych tematów — kliknij tutaj i zobacz szczegółowe opisy oraz darmowy webinar.
Trochę nieoptymalne to szukanie, po prostu 256 razy szuka xorując sobie bufor za każdym razem inną stałą. A wystarczyłoby wyliczyć stałą xorującą na podstawie kolejnych znaków z pliku xorując je z pierwszym znakiem szukanego stringu (pierwszy znak dla tej stałej już się będzie zgadzał).
A znasz bajke o Tymi Tu?
A jeszcze lepiej: zrobić xor sąsiednich znaków w pliku i szukanym tekście, wtedy można użyć dowolnego algorytmu szukania (np. użytego tam KMP). Oczywiście raz zamiast 256 razy.
A bajkę o Tymitumie znam, tylko jakoś nie widzę zastosowania ;)
Mik, mógłbyś rozwinąć te metody albo podrzucić link do jakichś materiałów???
Może zbyt skrótowo to wytłumaczyłem. Lepiej na przykładzie. Dla uproszczenia binarnie.
Plik: 10101001010101001001
Szukany string: 11011
Metoda 1:
Wiemy że szukany string zaczyna się od 1, więc stała xorująca na pierwszej pozycji pliku musi być 0 żeby szukany string mógł się tam znaleźć (bo w pliku jest tam też 1), dla drugiej pozycji pliku stała xorująca = 1 (bo w pliku jest 0) itd. Ogólnie stała xorująca = pierwszy znak szukanego stringu xor znak z pliku gdzie akurat spodziewamy się tego znaku.
Metoda 2:
Xorujemy sąsiednie znaki w pliku i szukanym stringu (skraca nam to oba o 1 znak):
Plik: 10101001010101001001 => 1111101111111101101
Szukany string: 11011 => 0110
no i “od razu widać” (znaczy się: używamy dowolnej metody szukania) że szukany string występuje pod koniec.
Dowód poprawności obu metod pozostawiam czytelnikowi :)