Wyszukiwanie powtórzeń wzorca o zadanej długości

Mam problem z implementacją pewnego algorytmu. Muszę zaimplementować wyszukiwanie wzorca (nie znamy treści) o zadanej długości znaków, najczęściej się powtarzającego. Przykładowo mamy ciąg znaków :

abczxcabczxabc

Tutaj najczęsciej występującym ciągiem był "abc" (zaraz po "zxc").

Gdyby chodziło tutaj o wyszukiwanie zadanego wzorca, to problem byłby banalny i poradziłbym sobie. Macie jakieś pomysły ?

Żeby nie było, że tylko zadaje pytania, rozmyślałem nad tym problemem. Mam pewne rozwiązanie w głowie tego problemu ale jest ono raczej głupie (iterowanie po każdym znaku, odkładanie do bufora po n znaków, potem wyliczanie częstotliwości występowania poszczególnych kombinacji).

Jeśli znamy długość wzorca którego szukamy to tka na prawdę możliwości wcale nie jest tak dużo. Mój pomysł jest taki: wybieramy z wejścia kolejne podciągi o zadanej długości i puszczamy http://pl.wikipedia.org/wiki/Algorytm_Karpa-Rabina żeby odszukać wszystkie wystąpienia tego podciągu. Dodatkowa optymalizacja jest taka że robimy sobie tablicę która odwzorowuje ciąg->ilość wystąpień. Zanim zaczniemy szukać danego ciągu to sprawdzamy czy czasami juz nie wystąpił wcześniej.

Z Algorytmu Rabina-Karpa przyda się tylko funkcja haszująca, jako że policzenie hasza od następnego podciągu da się zrobić w O(1) mając hasz aktualnego podciągu. Hasze posłużą jako indeksy w tablicy haszującej (mapie). Odwołanie do haszmapy kosztuje O(1), ale trzeba dodatkowo sprawdzić czy całe ciągi się zgadzają a nie tylko hasze więc odwołanie do haszmapy będzie pesymistycznie kosztowało O(długość wzorca).

Inne rozwiązanie z lepszą gwarantowaną złożonością.
Jeśli:

• n = długość tekstu,
• k = długość wzorca,

To za pomocą algorytmu QSufSort możemy wyznaczyć owy wzorzec w czasie O(n log k). W tym algorytmie w iteracji i-tej mamy posortowaną tablicę sufiksów po 2^{i pierwszych znakach, a iteracja trwa O(n). Gdy dojdziemy do iteracji takiej, że 2}i >= k to kończymy, a z posortowanych sufiksów łatwo wyciągnąć najczęściej powtarzający się.