Minimalny okres słowa - algorytm KMP

Witam.
Mam napisać program, który wyszukuje minimalny okres słowa. Zrobiłem to za pomocą KMP i MP, ale wciąż mam pewien problem, gdyż sprawdzarka która sprawdza poprawność zadania (zaznaczam, że nie chodzi o spoja) oznajmia iż program przekracza limit pamięci. I tu mam pytanie do was przyjaciele: czy da się to zrobić pomijając użycie tablicy prefikso-sufiksów?
Myślę, że to pozwoliłoby zjechać na pamięci.
Proszę o jakieś sugestie i pozdrawiam.
Dzięki :)

A jaki masz limit i jakie masz dane?

W największym teście jest limit 55MB.
A co do danych to: http://ideone.com/dRgAgl tutaj są przykładowe.

Wstępnie rozwiązanie może być takie:

• ciągu pomocniczego nigdzie nie zapisujesz, generujesz od razu ciąg główny,
• ciąg główny jest ciągiem zer i jedynek, a te możesz bezproblemowo zapakować do bajtów, dzięki czemu zamiast 16 mebagajtów używasz dwóch,
• maksymalna długość ciągu jest mniejsza niż 2^24, więc teoretycznie mógłbyś użyć 24-bitowego unsigned inta + atrybutów packed itd i tego używać, w sensie:

pragma<packed coś tam>
struct {
  unsigned int wartość : 24;
} mój_int;

• dzięki powyższemu trikowi tablica KMP zmniejsza się do 16 mln * 24 bity = 48 megabajtów,
• razem daje to 50 megabajtów i dzięki temu mieścisz się w limicie,
• pakowanie cyfr do bitów też możesz zrobić bit fieldami z C++a dzięki czemu kod będzie elegancki,

Jak jesteś hardkorem to możesz spróbować z algorytmem Galila-Seiferasa, który nie wymaga dodatkowej tablicy, a którą wymaga algorytm KMP.

Zobaczymy czy zadziała. Dzięki.

Super dzięki :) Pamięć zeszła w dół teraz tylko czasy przekracza, ale może coś wykombinujemy.

Prawdopodobnie to pakowanie intów powoduje problem wydajnościowy. Spróbuj zrobić pewną hybrydę:

• pierwsze np 2^20 elementów trzymaj jako zwykłe niespakowane inty,
• resztę trzymaj jako spakowane,

Poza tym: o ile przekracza?

Możesz jeszcze spróbować przyspieszyć generowanie ciągu głównego poprzez wykorzystanie: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556 jeżeli dzielenie jest wąskim gardłem przy liczeniu.
Prościej jest to opisane w http://agner.org/optimize/optimizing_assembly.pdf w paragrafie: Repeated integer division by the same value

Ale czasy przekraczało i bez tego pakowania. Tak że raczej to nie to. Możliwe że to przez vector? Używam vectora zamiast zwykłych tablic (bo potrzebuję implementacji bitów a ponoć vector jest wydajniejszy do takich operacji). Jeśli chcesz to mogę ci pokazać kod na priva.

Jeśli vector nic nie ułatwia w zadaniu na algorytmy to nie używaj wektora. W tym przypadku polecam użycie zwykłej tablicy, ale z dodatkami typu packed pragma coś tam bit field o których już tu wspomniałem :)

Przekracza czasy? No to może przez to liczenie ciągu głównego. Tam jest dzielenie modulo które może spowalniać mocno cały proces. Ten trik z optymalizacją który podałem powinien polepszyć czas, ale z drugiej strony raczej żaden ćwiczeniowiec/ wykładowca nie powinien takich rzeczy wymagać.