ALGORITM

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\begin{algorithm}[]
\caption{Алгоритм поиска по простому шаблону matchSimplePattern}\label{sa_simple_match}
\begin{algorithmic}[1]
\Function{match\_simple\_pattern}{$p$, $esa$, $prevbounds$, $maxpos$}
\State \Comment{$p$ - шаблон строки}
\State \Comment{$esa$ - улучшенный суффиксный массив}
\State \Comment{$prevbounds$ - границы для поиска в массиве}
\State \Comment{$maxpos$ - набор пар \mathtextpair{K}{MAXPOS}}
\Let{$newmaxpos$}{Nil} \label{sa_simple_match:initmaxpos}
\Let{$bounds$}{findFactorBounds($prevbounds$)} \label{sa_simple_match:factor}
\If{$bounds$ are empty}
\State \Return None \Comment{Шаблону ничего не соотвествует}
\EndIf
\Let{$newbounds$}{filter($bounds$, $esa$.suffix($esa$[$i$]).len >= p.len)} \label{sa_simple_match:filter}
\Comment{Получим границы для суффиксов, содержащих p как подстроку}
\If{$newbounds$ are empty}
\Let{lcp}{$bounds$}
\If{$esa$.suffix($esa$[$bounds$.first])[$\;$:$lcp$] = $p$[$\;$:$lcp$]} \label{sa_simple_match:first_cmp}
\State \Return MATCH\_SIMPLE\_PATTERN($p$[$lcp$:$\;$], $esa$, $bounds$, $maxpos$)
\Else
\State \Return None
\EndIf
\EndIf
\Let{$lcp$}{$esa$.lcp($newbounds$)} \Comment{Найдём lcp для подходящих суффиксов фактора}
\If {$esa$.suffix($esa$[$newbounds$.first])[$\;$:$lcp$] = $p$[$\;$:$lcp$]} \label{sa_simple_match:second_cmp}
\State \Comment{шаблон p полностью совпал с lcp для подходящих суффиксов}
\ForAll{$i$ in $newbounds$}
\Let{$suf$}{$esa$.suffix($esa$[$i$])}
\Let{$num$}{$esa$.strnum($suf$)}
\If{$maxpos$ contains $num$ and $maxpos$[$num$] >= $suf$.len + $p$.len}
\If{checkMatchConditions($p$, $suf$, $p$.type)} \label{sa_simple_match:check_match_conditions}
\Let{$newmaxpos$[$num$]}{$suf$.startindex}
\EndIf
\EndIf
\EndFor
\EndIf
\State \Return $newmaxpos$
\EndFunction
\end{algorithmic}
\end{algorithm}