appendix-b.tex

\section*{Приложение Б - Псевдокод алгоритма RKR-GST}
\addcontentsline{toc}{section}{Приложение Б - Псевдокод алгоритма RKR-GST}

Псевдокод для основного тела алгоритма
\newline
\begin{algorithm}[H]
	\SetAlgoLined %% Это соединяет линиями логические части

	search-length s := initial-search-length;

	stop := false;

	\Repeat{stop} {
		$L_{max}$ := scanpattern(s);

		\eIf{$L_{max}$ > 2 $\times$ s}{
			s := $L_{max}$;
		}{
			markstrings(s);

			\eIf{s > 2 $\times$ minimum\_match\_length}{
				s := s div 2;
			}{
				\eIf{s > minimum\_match\_length}{
					s := $minimum\_match\_length$;
				}{
					stop := true;
				}	
			}
		}
	}		
\end{algorithm}

\newpage
Псевдокод для функции $scanpattern()$
\newline
\begin{algorithm}[H]
	\small
	\SetAlgoLined

	\For{unmarked tokens $T_t$}{
		\eIf{distance to next tile $\le$ s}{
			advance $t$ to first unmarked token after next tile;
		}{
			create the KR hash-value for substring $T_t$ . . . $T_{t + s - 1}$ and add to hashtable;	
		}	
	}


	\For{unmarked tokens $P_p$}{
		\eIf{distance to next tile $\le$ s}{
			advance $p$ to first unmarked token after next tile;
		}{
			create the KR hash-value for substring $P_p$ . . . $P_{p + s - 1}$ and add to hashtable;

			check hashtable for hash of KR hash-value;

			\For{each hash-table entry with equal hashed KR hash-value}{
				
				k := s;

				\While{$P_{p + k} = T_{t + k} \ \& \ unmarked(P_p + k) \ \& \ unmarked(T_t + k)$}{
					k := k + 1;
				}
				\eIf{k > 2 $\times$ s}{
					return(k);
				}{
					record new maximal-match;			
				}	
			}
		}	
	}
	return(length of longest maximal-match);
\end{algorithm}

\newpage
Псевдокод для функции $markstrings()$
\newline
\begin{algorithm}[H]
	\small
	\SetAlgoLined

	\While{$queue\ non-empty$}{
		\eIf{$current\ queue\ is\ empty$}{
			drop to next queue;
		}{
			remove match(p, t, L) from queue;

			\eIf{$match\ not\ occluded$}{
				\For{$j\leftarrow 0$ \KwTo $s-1$}{
					\eIf{$P_{p+j} = T_{t+j}$}{
						\For{$i\leftarrow 0$ \KwTo $s-1$}{
							mark\_token($P_{p + i}$);

							mark\_token($T_{p + i}$);
						}

						$length\_of\_tokens\_tiled := length\_of\_tokens\_tiled + L$;
					}							
				}		
			}{
				\eIf{$L - L_{occluded} \ge s $}{
					replace unmarked portion on list of queues;
				}			
			}	
		}	
	}
 \end{algorithm}