prev符号¶
パラメタ化照合を効率よく行うための符号化．
文字列 \(T\) をprev符号化した文字列を \(\langle T \rangle\) と表す．
\(\langle T \rangle\) の定義は次の通りである．
\[\begin{split}\langle T \rangle [i] =
\begin{cases}
T[i] & \text{$T[i] \in \Sigma$} \\
0 & \text{$T[i] \in \Pi \ and \ T[i] \neq T[j]\ for \ any \ 1 \le j < i$} \\
i-k & \text{$T[i] \in \Pi \ and \ k = max\{j:T[j] = T[i]\ and \ a \le j < i\}$}
\end{cases}\end{split}\]