Informatyka MIMUW

Pokażemy teraz wersję algorytmu on-line, która działa w czasie rzeczywistym, tzn. czas reakcji między wczytaniem symbolu a daniem odpowiedzi jest O(1), niezależnie od rozmiaru alfabetu. Zamiast KMP użyjemy algorytm MP, którego preprocessing jest prostszy.

Algorytm zachowuje się podobnie jak algorytm On-Line-KMP; podstawowa różnica polega na tym, że algorytm wkłada do kolejki wczytane symbole, które jeszcze nie są przetworzone w sensie algorytmu MP. Rysunek pokazuje relacje tego algorytmu do algorytmu MP. Symbole z wejścia najpierw wędrują do kolejki.

Rysunek 2: Typowa konfiguracja w algorytmie real-time-MP.

Algorytm Real-Time-MP

  inicjalizacja:  j:=0; Kolejka := emptyset; 
  repeat forever (niezmiennik: |Kolejka| \le (m-j)/2 ) 
    read(symbol); 
    insert(symbol,Kolejka); 
    write(OUTPUT(Kolejka, j));

W celu skrócenia zapisów pojedynczych algorytmów rozbijamy algorytm na dwie części. Zasadnicza część jest zapisana jako osobna funkcja OUTPUT(Kolejka, j). Wynikiem funkcji jest 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpienie wzorca x. Zmienne Kolejka, j są globalne. Oczywiste jest, że opóźnienie (czas reakcji) tego algorytmu jest O(1).
Algorytm OUTPUT(Kolejka, j)

  output  :=  0; (początkowo Kolejka niepusta)
  repeat 2 times
    if  Kolejka niepusta then
      if  j=-1  then 
        j  :=  0; delete(Kolejka); 
      else if  x[j+1] <> first(Kolejka) then  j:=P[j]; 
      else 
        j:=j+1; delete(Kolejka); 
      if  j=m  (w tym momencie  Kolejka=emptyset) 
       output := 1; j := P[m];  
 return(output);