May 2017
6 / 6
May 2017
May 2017
loginus
May '17
2

Pewnie można i haszowaniem rozwiązać - ja jednak poszedłem jak elektron najmniejszą linią oporu czyli na łatwiznę i zwykła pętla porównująca wzorzec ze źródłem wystarczyła .

W funkcji pot_szybkie masz return w%q; -- a potem i tak jeszcze raz robisz
h = pot_szybkie(p, dl_a - 1, q) % q;

a *= a; tu tez powinno być dzielenie modulo

Dla takich danych :

1
26
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz

Program zwraca zły wynik .

jedrzejd
May '17

Moim zdaniem to jest dziwne ci przeszła O(n*m)
a mi jeżeli sprawdzam jeszcze jak hasze są równe wzorce to mam TLE a jak nie to mam AC???
O co tu chodzi te rozwiazanie z jeszcze spr wzorca działa w najgorszym czasie O(n*m)
Wrzucam kod do obejrzenia
KOD10

loginus
May '17
  • 0.28 sek - czas mojego algorytmu o złożoności O(n*m)

Link jest chyba nieprawidłowy bo ideone pokazuje mi tylko pustą stronę . Wrzuć jeszcze raz na ideon.

Możliwe że któryś test jest bardzo długi np ma 2 miliony liter w teksie do wyszukania , a w twoim kodzie jest założenie że

char a[1000000], b[1000000]

wtedy albo utnie część danych albo wyrzuci błąd pamięci .

loginus
May '17

Dla danych :

1
0

aaaaaa

Błędny wynik .

"Trzeci wiersz zawiera test T czyli ciąg liter alfabetu angielskiego zakończony znakiem nowego wiersza."

Zakładasz że dane wejściowe w drugim wierszu mają długość mniejszą od milion plus 1 .
Autor zadania pisze tylko że wiersz kończy się enterem .

char a[1000002],b[1000002];
scanf("%s",b);

Co jak wiersz będzie miał większą długość ??

Przy haszowaniu zawsze jest możliwość kolizji - więć gdy
if(hasz1==hasz2){
wtedy lepiej sprawdzić czy łańcuch znaków w tekście od pozycji n-tej jest równy wzorcowi - nie spowolni to algorytmu ( o ile kolizje są rzadkie ) a jest zawsze 100 procent pewności .
Czyli to co w kodzie jest zaznaczone jako komentarz lepiej pozostawić jako działający kod .