Informatyka MIMUW

Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole \( y \) i wypisujemy on-line (na bieżąco) odpowiedź:

• 0 - gdy dotychczas wczytany tekst nie zawiera x jako sufiks,
• 1 - jeśli zawiera

Algorytm On-Line-KMP

j:=0;  
repeat forever 
    read(symbol); 
    while j > -1 and x[j+1] <> symbol do j:=P'[j]; 
    j:=j+1; 
    if j=m then 
      write(1);  j := P'[m]; 
    else write(0);

Oznaczmy przez delay(m) maksymalną liczbę kroków algorytmu On-Line-KMP między wczytaniem symbolu i daniem odpowiedzi. Przez delay'(m) oznaczmy podobną wielkość, w sytuacji gdy zamiast tablicy P' użyjemy P.

Przykład

Jeśli \( x=aaaa\dots a \) oraz \( y=a^{m-1}b \), to \( delay(m)=O(1) \), \( delay'(m)=\Theta(m) \).

Z lematu o okresowości wynika, że zachodzi następujący fakt:

\( delay(m)\ =\ \Theta(\log m) \)

Uzasadnienie pozostawiamy jako ćwiczenie.