Двусторонний алгоритм

Двусторонний алгоритм (англ. Two Way algorithm) — алгоритм поиска подстроки в строке.

Характерные черты

• требует упорядоченный алфавит
• этап предобработки занимает $O(m)$ времени и константное количество памяти
• этап поиска за время $O(n)$
• в худшем случае производится $2n - m$ сравнений символов

Описание алгоритма

Строка $x$ разбивается на две части $x_l$ и $x_r$ так, что $x=$ $x_l$ $x_r$. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов $x_r$ слева направо, и затем, если на этом первом этапе не происходит несовпадений, в сравнении символов $x_l$ справа налево (второй этап). Фаза предобработки, таким образом, заключается в поиске подходящего разбиения $x_l$ $x_r$.

Определение:

Пусть $(u, v)$ — разбиение $x$. Повторение в $(u, v)$ — слово $w$ такое, что для него выполнены следующие условия: $w$ — суффикс $u$ или $u$ — суффикс $w$; $w$ — префикс $v$ или $v$ — префикс $w$. Длина повторения в $(u, v)$ называется локальным периодом; наименьший локальный период записывается как $r(u, v)$. Каждое разбиение $x$ на $(u, v)$ имеет как минимум одно повторение. Очевидно, что $1 \leqslant r(u, v) \leqslant |x|$ Разбиение $x$ на $(u, v)$ такое, что $r(u, v) = per(x)$ называется критическим разбиением $x$.

Если $(u, v)$ — критическое разбиение $x$, то на позиции $|u|$ в $x$ общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение $(x_l, x_r)$ такое, что $|x_l| \lt per(x)$ и длина $|x_l|$ минимальна. Чтобы найти критическое разбиение $(x_l, x_r)$ мы сперва вычислим $z$ — максимальный суффикс $x$ в порядке $\leqslant$ и максимальный суффикс $\widetilde{z}$ для обратного порядка $\geqslant$. Затем $(x_l, x_r)$ выбираются так, что $|x_l| = \max(|z|, |\widetilde{z}|)$.

Фаза поиска в двустороннем алгоритме состоит из сравнения символов $x_r$ слева направо и символов $x_l$ справа налево. Когда происходит несовпадение при просмотре $k$-го символа в $x_r$, производится сдвиг длиной $k$. Когда происходит несовпадение при просмотре $x_l$, или когда образец встретился в строке, производится сдвиг длиной $per(x)$. Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной $per(x)$, длина совпадающего префикса образца в начале "окна" (а именно $m - per(x)$) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.

Псевдокод

function twoWaySearch(String pattern, String text):
    n = pattern.length
    $\langle$len1, p1$\rangle$ $\leftarrow$ maxSuffix(pattern, $\leqslant$)
    $\langle$len2, p2$\rangle$ $\leftarrow$ maxSuffix(pattern, $\geqslant$)
    if len1 $\geqslant$ len2
        len = len1
        p = p1
    else
        len = len2
        p = p2
    occurences = $\varnothing$
    pos $\leftarrow$ 0
    memPrefix $\leftarrow$ 0
    if len < n/2 and pattern[1$\ldots$len] $-$ суффикс pattern[len + 1$\ldots$len + p]
        while pos + n $\leqslant$ text.length
            i $\leftarrow \max$(l, memPrefix) + 1
            while i $\leqslant$ n and pattern[i] $=$ text[pos + i]
                i++
            if i $\leqslant$ n
                pos $\leftarrow$ pos + $\max$(i $-$ len, memPrefix $-$ p $+$ 1)
                memPrefix $\leftarrow$ 0
            else
                j $\leftarrow$ l
                while j $\gt$ memPrefix and pattern[j] $=$ text[pos + j]
                    j--
                if j $\leqslant$ memPrefix
                    pos $\rightarrow$ occurences
                pos $\leftarrow$ pos $+$ p
                memPrefix $\leftarrow$ n $-$ p
    else
        q $\leftarrow \max$(len, n $-$ len) $+$ 1
        while pos + n $\leqslant$ text.length
            i $\leftarrow$ len + 1
            while i $\leqslant$ n and pattern[i] $=$ text[pos $+$ i]
                i++
            if i $\leqslant$ n
                pos $\leftarrow$ pos $+$ i $-$ len
            else
                j $\leftarrow$ len
                while j $\gt$ 0 and pattern[j] $=$ text[pos $+$ j]
                    j--
                if j $=$ 0
                    pos $\rightarrow$ occurences
                pos $\leftarrow$ pos $+$ q
    return occurences

Источники информации

• Оригинал статьи (M. Crochemore, D. Perrin)
• Краткое описание алгоритма, пример работы