Randomized String Ricerca

Question

Ho bisogno di rilevare se un binario modello $ P $ di lunghezza $ m $ si verifica in un testo binario $ T $ di lunghezza $ n $ dove $ m

Voglio affermare un algoritmo che viene eseguito in tempo $ O (n) $ in cui si assume che le operazioni aritmetiche su $ O (\ log_2 n) $ numeri di bit può essere eseguito in tempo costante. L'algoritmo dovrebbe accettare con probabilità $ 1 $ ogni volta che $ P $ è una sottostringa di $ T $ e rifiutare con probabilità di almeno $ 1 -. \ Frac {1} {n} $ altrimenti

Credo che le impronte digitali potrebbe aiutare qui. Ma io non riesco a farlo.

Answer 1

Il Knuth-Morris-Pratt algoritmo fa in tempo lineare senza alcun errore.