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

Двусторонний алгоритм (англ. Two-Way String-Matching algorithm) — алгоритм поиска подстроки в строке, разработанный и представленный Максимом Крочемором (Maxime Crochemore) и Домиником Перреном (Dominique Perrin) в 1991 году.[2] Относится к группе алгоритмов поиска подстроки с ограниченным потреблением памяти, константным на практике (constant-space string matching).

По заданной строке Text длины n и шаблону поиска Pattern длины m алгоритм позволяет найти все вхождения Pattern в Text за время ${O(n+m)}$, где ${O(m)}$ — этап предварительных вычислений над шаблоном, а ${O(n)}$ — этап поиска. При этом, во время поиска выполняется не более ${2n-m}$ операций сравнения.

В отличие от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура, данный алгоритм требует ${O(\log(m))}$ памяти: на этапе препроцессинга строка шаблона разбивается на 2 подстроки и хранится только позиция этого разбиения. Численное значение этой позиции меньше длины шаблона $m$, поэтому требование по памяти может быть представлено как ${\lceil\log_2m\rceil}$ бит и на практике может быть взято за ${O(1)}$.

Другое отличие данного алгоритма заключается в том, что ему требуется упорядоченный алфавит, так как во время препроцессинга символы сравниваются на больше и меньше.

Алгоритм в целом считается достаточно эффективным и благодаря тому, что потребление памяти практически не зависит от длины текста или шаблона, он используется в реализациях функций strstr(), memem() некоторых вариантов библиотек libc: glibc, newlib musl при достаточно длинной строке шаблона.

Общая схема #

Сканирование строки на этапе поиска двустороннего алгоритма похоже на сканирование в примитивном алгоритме, алгоритмах Кнута-Морриса-Пратта и Бойера-Мура.

В алгоритме Кнута-Морриса-Пратта строка сканируется слева направо, сравнение символов шаблона с символами текста также выполняется слева направо. Когда происходит несовпадение в какой-то позиции шаблона (либо все символы шаблона равны и найдено вхождение), шаблон сдвигается вправо на несколько позиций по заранее вычисленной таблице сдвигов паттернов поиска.

В алгоритме Бойера-Мура строка также сканируется слева направо, но символы шаблона сравниваются справа налево. При встрече несовпадающего символа, шаблон сдвигается на смещение, которое вычисляется как максимальное по 2 эвристикам: правилу сдвига плохого символа и правилу хорошего суффикса.

В двустороннем алгоритме строка шаблона делится на 2 подстроки: $u$ и $v$. Сначала сравнивается правая подстрока $v$ слева направо, затем, если все символы правой подстроки совпали, то сравнивается левая подстрока $u$ справа налево. Если встречается несовпадающий символ, то шаблон сдвигается вправо на некоторое количество позиций. Правила сдвигов при несовпадении разные для правой и левой части разбиения. Величина сдвига вычисляется за константное время и константную память.

Общую схему для сканирования можно представить следующим псевдокодом:

fun stringMatching(text, pattern): Boolean {
    val n = text.length
    val m = pattern.length
    val (u, v) = factorize(pattern)

    var pos = 0, i = u.length
    while (pos <= n-m) {
        // Сравнение правой части
        while (i < m && pattern[i] == text[pos + i]) i += 1

        if (i == m) {
            // Сравнение левой части
            if (text.substring(pos .. pos + u.lastIndex) == u) {
                return true
            }
        }
        (pos, i) = shift(pos, i)
    }
    return false
}

factorize() — функция разбиения шаблона на 2 подстроки. Двусторонний алгоритм использует разбиение шаблона на подстроки, называемый критическим разбиением (Critical Factorization) и базируется на теореме о критическом разбиении (Critical Factorization Theorem).
shift() — правила сдвигов. Двусторонний алгоритм выбирает разбиение строки ${x = uv}$, такое, что длина левой подстроки $u$ меньше глобального периода строки шаблона (${|u| < per(x)}$), длина $u$ минимальна, а правая подстрока $v$ периодична.

Есть также другой алгоритм, относящийся к алгоритмам с ограниченным потреблением памяти и работающий по такой же схеме — это алгоритм Галиля — Сейфераса (Galil - Seiferas) [1], [4]. В нем используется разбиение, называемое идеальным разбиением (perfect factorization). Выбирается позиция, где начинается наиболее часто повторяющаяся подстрока шаблона.

Базовые понятия #

Зададим некоторые связанные со строками базовые определения, которые понадобятся в описании алгоритма.

Алфавит

Алфавит (alphabet) — это конечное непустое множество символов. Обозначим его через $A$. Примеры наиболее часто используемых алфавитов:

• ${A = \\\{\text{a,b,…, z}\\\}}$ — множество строчных букв английского алфавита
• ${A = \\\{\text{0,1,2,3,4,5,6,7,8,9}\\\}}$ — множество цифр
• ${A = \\\{\text{0,1}\\\}}$: бинарный алфавит

и т.п.

Строка

Строка (текст, слово) (string, text, word) — конечная последовательность символов из некоторого алфавита $A$. Длина строки — это количество элементов в последовательности. Например, длина строки “${\tt{ABCDEF}}$” равна 6.

Введем следующие обозначения для некоторый строки $x$:

${|x|}$ ­— длина строки $x$.
${x[i]}$ — ${(i+1)}$-ый символ строки (считаем, что первый символ находится по индексу 0).
${x[i…j]}$ — подстрока ${x[i]x[i+1]…x[j]}$ строки $x$.

Пустую строку обозначим через $ε$. Множество всех последовательностей алфавита $A$ — через ${A^{*}}$, а множество всех непустых строк — через ${A^{+}}$.

Подстрока

Строка $x$ длины $n$ является подстрокой (или фактором) (factor, subword) строки $y$, если ${x=y[i … i+n-1]}$ для некоторого целого $i$. Мы можем говорить, что подстрока $x$ встречается в строке $y$ в позиции $i$. Стоит отметить, что подстрока — это не то же самое, что и подпоследовательность.
Строка $x$ является подпоследовательностью (subsequence) строки $y$, если она может быть получена удалением из $y$ нуля или более (не обязательно смежных) символов. Другими словами, если ${x=y[i₁]y[i₂]…y[i_m]}$, где ${i₁, i₂, i_m}$ — увеличивающаяся последовательность индексов строки $y$.

Операции над строками

Конкатенацией двух строк $x$ и $y$ называют строку с последовательной записью их символов. Обозначим конкатенацию строк $x$ и $y$ как $xy$. Например, если ${x=\texttt{AB}, y=\texttt{CD}}$, то ${xy=\tt{ABCD}}$.
Через ${k^x}$ обозначим конкатенацию $k$ копий строки $x$. Например, для ${x=\tt{AB}}$, ${x⁴=\tt{\underlinesegment{AB}\underlinesegment{AB}\underlinesegment{AB}\underlinesegment{AB}}}$. Стоит отметить, что конкатенация ассоциативна, т.е. ${(xy)z = x(yz)}$, поэтому скобки здесь не обязательны и выражение можно записать как ${xyz}$.

Рассмотрим строку ${x = uvw}$, представляющую из себя композицию из 3 подстрок: $u$, $v$ и $w$. Подстроки $u$, $v$ и $w$ называются факторами строки $x$. Кроме того:
$u$ — это префикс строки $x$,
$w$ — это суффикс строки $x$.

Префикс

Строка $u$ называется префиксом (prefix) строки $x$, если существует такая строка $v$, что ${x=uv}$. Например, ${\tt ABC}$ — это префикс строки ${\tt \underlinesegment{ABC}DAB}$. Префикс можно рассматривать как особый случай подстроки. Обычный префикс может быть как пустой строкой (ε), так и всей строкой.
Собственный префикс (proper prefix) — это префикс с дополнительными ограничениями: он не может быть пустым и не может быть равен всей строке целиком.

Суффикс

Строка $w$ называется суффиксом (suffix) строки $x$, если существует такая строка $v$, что ${x=vw}$ Например, ${\tt DAB}$ — суффикс строки ${\tt ABC\underlinesegment{DAB}}$. Также, как и в случае с префиксом, обычный суффикс может быть как пустым, так и всей строкой.
Собственный суффикс (proper suffix) — это суффикс, который не может быть равен пустой строке и всей строке целиком.

Период

Период (period) строки $x$ — это целое число $p$, ${1<p≤|x|}$ такое, что ${∀i∈\\{0,1,…|x|-p-1\\}x[i]=x[i+p]}$
Проще говоря, это длина постоянно повторяющегося фрагмента текста, причем, последнее вхождение может быть “обрезано”. Например, строка ${\tt{AABAAABAA}}$ (её длина равна 9), имеет периоды 4, 7, 8 и 9:

$\begin{aligned} & \tt{\large{\underbrace{AABA}_4\underbrace{AABA}\underbrace{A\phantom{ABA}}}} \\\\ & \tt{\large{\underbrace{AABAAAB}_7\underbrace{AA\phantom{BAAAB}}}} \\\\ & \tt{\large{\underbrace{AABAAABA}_8\underbrace{A\phantom{ABAAABA}}}} \\\\ & \tt{\large{\underbrace{AABAAABAA}_9}} \end{aligned}$

Отметим, что длина строки всегда является её периодом, а это значит, что любой строки всегда есть хотя бы один период.
Обозначим наименьший период строки $x$ через ${per(x)}$ (численное значение), а саму подстроку наименьшего периода — через ${period(x)}$.

Возьмем непустую строку $x$ и какое-то число $p$ такое, что ${0<p≤|x|}$. Во всех следующих случаях $p$ будет периодом строки $x$:

1. Если $x$ — это подстрока некоторой строки ${y^k}$, где ${|y|=p}$ и ${k>0}$.
   Пример
   ${y^k=\underbrace{\texttt{ABC}}_y\underbrace{\tt{ABC}}_y\underbrace{\texttt{ABC}}_y\underbrace{\texttt{ABC}}_y} \qquad y=\texttt{ABC} \quad {p=3} \quad {k=4}$
   Если взять за $x$ любой префикс или подстроку (фактор) строки ${y^k}$, то один из её периодов будет тоже 3.

2. Если строку $x$ можно представить как ${(uv)^ku}$, где ${|uv|=p}$, строка $v$ — непустая и ${k>0}$
   Пример
   ${x = \underbrace{\texttt{ABC}}_u\underbrace{\texttt{DEFG}}_v\underbrace{\texttt{ABC}}_u\underbrace{\texttt{DEFG}}_v\underbrace{\texttt{ABC}}_u}$
   ${u=\texttt{ABC}}, \space {v=\texttt{DEFG}}$
   ${x=(uv)²u}$
   ${|uv|=7}, \space {p=7}$

3. Возьмем некоторые строки $y$, $z$ равной длины и строку $w$, такие, что ${x=yw=wz}$; ${|y|=|z|}$. В этом случае длина $y$ и $z$ будет периодом строки $x$: ${|y|=|z|=p}$.
   Пример
   ${x=\mathrlap{ \overbrace{\phantom{\mathtt{ABCDAB}}}^w \overbrace{\phantom{\mathtt{ABCD}}}^z } \underbrace{\mathtt{ABCD}}_y\underbrace{\mathtt{ABCDAB}}_w }$
   ${y=\tt ABCD}$
   ${z=\tt CDAB}$
   ${w=\tt ABCDAB}$
   ${p=|y|=|z|=4}$

Грань

Грань (также граница или бордер) (border) строки $x$ — это любой собственный префикс строки, который равен её суффиксу. Т.е. грань — это такая строка $w$, что ${x=yw=wz}$. Грань не может быть равна всей строке, но суффикс и префикс строки могут быть перекрывающимися. Например, грани строки ${\tt AABAAABAA}$: ${\tt AABAA, AA, A, ε}$.

Обозначим наибольшую грань строки $x$ через ${Border(x)}$. Мы можем рассматривать такую грань как наибольшее совпадающее пересечение при наложении строки самой на себя.
Строка $x$ свободна от граней (border free), если наибольшая грань строки — это пустая строка, или другими словами, если наименьший период равен длине строки (${per(x)=|x|}$)
Между гранями и периодами имеется взаимно однозначное соответствие, это можно увидеть по пункту 3 из описания периода.

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

Пусть $x$ — непустая строка, а ${uv}$ — разбиение $x$. Обозначим через $l$ длину левой части разбиения минус 1 (${l = |u| - 1}$). ${0≤l<|x|}$.
Непустая строка $w$ называется повторением для разбиения $\textit{\textbf{uv}}$ (repetition for factorization) или повторением в позиции $\textit{\textbf{l}}$ строки $\textit{\textbf{x}}$, если выполняются оба условия:

• $w$ — суффикс $u$ или $u$ — суффикс $w$
• $w$ — префикс $v$ или $v$ — префикс $w$

Базовый случай повторения ($w$ — суффикс $u$ и $w$ — префикс $v$) — это когда разбиение между $u$ и $v$ — это центр квадрата где-то в строке $x$:

Другие случаи соответствуют ситуациям, когда $l$ находится близко к краям строки или при переполнении $w$. Стоит заметить, что если есть строка ${x=uv}$, а в качестве $w$ взять строку $vu$, то эта строка $w$ будет повторением для разбиения $uv$ (выполнятся оба условия). Т.е. любое разбиение непустой строки $x$ всегда имеет хотя бы одно повторение.

Длина $r$ повторения для разбиения $uv$ называется локальным периодом $\textit{\textbf{uv}}$ или локальным периодом строки $\textit{\textbf{x}}$ в позиции $\textit{\textbf{l}}$. Другими словами, число $r$ является локальным периодом строки $x$ в позиции $l$, если ${x[i]=x[i+r]}$ для всех индексов ${l-r+1≤i≤l}$ и выполняются оба условия повторения.

Наименьшее возможное значение локального периода для разбиения ${uv}$ обозначается как ${r(u,v)}$.

Примеры

Пусть строка ${x=\texttt{ABAABAA}}$.

Рассмотрим наименьший локальный период в позиции ${l=2}$:

${ \gdef\string_idx#1{\color{aaaaaa} \tt #1} \mathrlap{ \overbrace{\phantom{ \def\arraystretch{1.3}\begin{array}{c c c} \string_idx{0} & \string_idx{1} & \tt 2 \\\\ \tt A & \tt B & \tt A \end{array} } \hspace{0.4em} }^u \overbrace{\phantom{ \def\arraystretch{1.3}\begin{array}{c c c} \string_idx{3} & \string_idx{4} & \string_idx{5} \\\\ A & B & A \end{array} } \hspace{1.3em} }^v } \def\arraystretch{1.3}\begin{array}{c:c:c|c:c:c:c} \tt \string_idx{0} & \string_idx{1} & \tt 2 & \string_idx{3} & \string_idx{4} & \string_idx{5} & \string_idx{6} \\\\ \hdashline \tt A & \tt B & \tt \underlinesegment{A} & \tt \underlinesegment{A} & \tt B & \tt A & \tt A \end{array}}$

$r(\texttt{ABA}, \texttt{ABAA}) = |\texttt{A}| = 1$,
наименьшее повторение $w=\texttt{A}$.

Рассмотрим наименьший локальный период в позиции ${l=1}$:

${ \gdef\string_idx#1{\color{aaaaaa} \tt #1} \mathrlap{ \underbrace{ \hspace{1.05em} \phantom{ \def\arraystretch{1.3}\begin{array}{c c} \string_idx{0} & 1 \\\\ \tt A & \tt B \end{array} } }_w \underbrace{ \phantom{ \def\arraystretch{1.3}\begin{array}{c c c} \string_idx{2} \string_idx{3} \string_idx{4} \\\\ \tt A & \tt A \tt B \end{array} } }_w } \hspace{1em} \def\arraystretch{1.3}\begin{array}{c:c|c:c:c:c:c} \string_idx{0} & 1 & \string_idx{2} & \string_idx{3} & \string_idx{4} & \string_idx{5} & \string_idx{6} \\\\ \hdashline \tt A & \tt B & \tt A & \tt A & \tt B & \tt A & \tt A \end{array} }$

${r(\texttt{AB}, \texttt{AABAA}) = |\texttt{AAB}| = 3}$,
наименьшее повторение ${w=\texttt{AAB}}$.

Пусть строка ${x=\tt AABABAB}$

Рассмотрим наименьший локальный период в позиции ${l=5}$:

${ \gdef\string_idx#1{\color{aaaaaa} \tt #1} \mathrlap{ \hphantom{ \def\arraystretch{1.3}\begin{array}{c c c c} \string_idx{0} & \string_idx{1} & \string_idx{2} & \string_idx{3} \end{array} } \underbrace{ \phantom{ \def\arraystretch{1.3}\begin{array}{c c} \string_idx{4} \\\\ \tt B & \tt \hspace{0.6em} \end{array} } }_w \underbrace{ \phantom{ \def\arraystretch{1.3}\begin{array}{c} \string_idx{6} \\\\ \tt B \end{array} \hspace{0.6em} } }_w } \def\arraystretch{1.3}\begin{array}{c:c:c:c:c:c|c} \string_idx{0} & \string_idx{1} & \string_idx{2} & \string_idx{3} & \string_idx{4} & \texttt{5} & \string_idx{6} \\\\ \hdashline \tt A & \tt A & \tt B & \tt A & \tt B & \tt A & \tt B \end{array} }$

${r(\texttt{AABABA}, \texttt{B}) = |\texttt{BA}| = 2}$,
наименьшее повторение ${w=\texttt{BA}}$.

Рассмотрим наименьший локальный период позиции ${l=1}$:

${ \gdef\string_idx#1{\color{aaaaaa} \tt #1} \mathrlap{ \underbrace{ \phantom{ \def\arraystretch{1.3}\begin{array}{c c c c c} \string_idx{3} \string_idx{2} \string_idx{1} \string_idx{0} 1 \\\\ \tt B & \tt A & \tt B & \tt A & \tt A \end{array} } }_w \underbrace{ \phantom{ \def\arraystretch{1.3}\begin{array}{c c c c c} \string_idx{2} \string_idx{3} \string_idx{4} \string_idx{5} \string_idx{6}\\\\ \tt B & \tt A & \tt B & \tt A & \tt B \end{array} } }_w } \hspace{6.6em} \def\arraystretch{1.3}\begin{array}{c:c|c:c:c:c:c} \string_idx{0} & 1 & \string_idx{2} & \string_idx{3} & \string_idx{4} & \string_idx{5} & \string_idx{6} \\\\ \hdashline \tt A & \tt A & \tt B & \tt A & \tt B & \tt A & \tt B \end{array} }$

${r(\texttt{AA}, \texttt{BABAB}) = |\tt BABABAA| = 7}$,
наименьшее повторение ${w=\texttt{BABABAA}}$.

Наименьший локальный период разбиения ${x=uv}$ не может быть больше глобального периода строки: ${1≤r(u,v)≤v}$, это следует из определений.

Разбиение ${x=uv}$, при котором наименьший локальный период равен глобальному периоду всей строки ${r(u,v)=per(x)}$ называется критическим разбиением (critical factorization), а позиция ${l=|u|-1}$ — критической позицией $\textit{\textbf{x}}$ (critical position).

Пример

Пусть ${x=\tt \underlinesegment{AABABAB}AAB}$.
Глобальный период строки $x$: 7 (${\tt AABABAB}$)
Локальные периоды для каждой позиции разбиения показаны в следующей таблице:

${\def\arraystretch{1.3}\begin{array}{r|c:c:c:c:c:c:c:c:c:c} \text{Строка} & \tt A & \tt A & \tt B & \tt A & \tt B & \tt A & \tt B & \tt A & \tt A & \tt B \\\\ \hdashline \text{Позиция разбиения }l & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\\ \hdashline \text{Лок. период }r(u,v) & 1 & \underline{7} & 2 & 2 & 2 & 2 & \underline{7} & 1 & 3 & 1 \end{array} }$

Критические разбиения: ${(\texttt{AA}, \texttt{BABABAAB})}$ и ${(\texttt{AABABAB}, \texttt{AAB})}$.

В двустороннем алгоритме в качестве разбиения для строки шаблона используется критическое разбиение, при этом длина левой подстроки меньше глобального периода всей строки шаблона (${|u| < per(pattern)}$).

Используются следующие правила сдвигов:

• При несовпадении в процессе сравнения правой подстроки шаблон сдвигается вправо на количество просканированных символов, так, чтобы позиция разбиения шаблона оказалась на позиции несовпадающего символа:

• При несовпадении в процессе сравнения левой подстроки шаблон сдвигается на глобальный период шаблона ${per(pattern)}$:

Такие правила сдвигов приводят к квадратичной сложности в худшем случае. Для улучшения асимптотической сложности худшего случая, в алгоритме также используется техника запоминания префикса (prefix memorization): когда производится сдвиг на ${per(pattern)}$ по правилу сдвига для левой подстроки, дополнительно запоминается префикс совпавшей части шаблона, чтобы не сравнивать его ещё раз в следующем цикле.
Это та же техника, которая используется в модификации алгоритма Бойера-Мура с добавлением правила Галиля (Wikipedia).

Ниже представлена первый вариант двустороннего алгоритма. Считаем, что глобальный период строки шаблона ${per(pattern)}$ и критическое разбиение ${uv}$ с ${|u|<per(pattern)}$ вычислены заранее.

Код на kotlin, без обработки суррогатных пар.

data class Factorization(val left: IntRange, val right: IntRange)

/**
 * Возвращает позиции всех вхождений шаблона [pattern] в строке [text]
 */
fun cp1(text: String, pattern: String): List<Int> {
    val result = mutableListOf<Int>()

    // factorize() разбивает строку шаблона pattern на 2 подстроки:
    // left и right так, что |left| < period.
    // left, right - закрытые диапазоны индексов соответствующих подстрок
    // period - глобальный период строки шаблона
    val (left, right) = factorize(pattern)
    val period = pattern.getMinimalPeriod()

    var pos = 0
    var memPrefix = -1
    while (pos + pattern.length <= text.length) {
        // Сравнение правой части
        val i = (maxOf(right.first, memPrefix + 1)..right.last).find{ i->
            pattern[i] != text[pos + i]
        }
        if (i != null) {
            pos = pos + i - right.first + 1
            memPrefix = -1
        } else {
            // Сравнение левой части
            val match = (left.last downTo memPrefix + 1).all { j ->
                pattern[j] == text[pos + j]
            }
            if (match) result.add(pos)
            pos += period
            memPrefix = pattern.length - period - 1
        }
    }
    return result
}

memprefix — позиция запомненного префикса, обновляется при встрече несовпадающих символов. Может быть установлена в неотрицательное значение только при сканировании левой подстроки.

Лемма

Пусть ${uv}$ — критическое разбиение строки $x$. Если $w$ — суффикс $u$ и $w$ — префикс $v$ (базовый случай), то длина $w$ кратна глобальному периоду строки $x$.

Доказательство корректности алгоритма есть в [1]. В таком виде алгоритм использует максимум ${2*|text|}$ операций сравнения. (доказательство там же).

Глобальный период строки шаблона требуется только тогда, когда он относительно не большой (меньше примерно половины длины шаблона), в остальных случаях можно обойтись без его вычисления.

Второй вариант двустороннего алгоритма рассчитан на применение при большом периоде строки шаблона. Дополнительное его преимущество — относительно небольшое максимальное количество сравнений.

Вариант отличается от первого тем, что в нем больше не используется запоминание префикса, а при несовпадении в левой подстроке используется другое правило — шаблон сдвигается не на ${per(pattern)}$ позиций, а на некоторое количество $q$, которое может быть меньше глобального периода (${q ≤ per(pattern)}$).
Если взять в качестве значения ${q=1}$, то алгоритм станет аналогичен наивному алгоритму с квадратичной сложностью, поэтому число $q$ выбирается с дополнительным ограничением: ${q > \max(|u|, |v|)}$, где ${uv}$ — критическое разбиение ${pattern}$. В таком виде число сравнений во втором варианте по прежнему будет меньше ${2*|text|}$, как и в первом, но вычисление глобального периода не потребуется.
Запоминание префикса в данном случае не может быть применено из-за того, что $q$ может быть меньше ${per(pattern)}$.

fun twoWay2(text: String, pattern: String): List<Int> {
    val result = mutableListOf<Int>()

    val (left, right) = factorize(pattern)
    val q = maxOf(left.length, right.length) + 1

    var pos = 0
    while (pos + pattern.length <= text.length) {
        // Сравнение правой части
        val i = right.find { i -> pattern[i] != text[pos + i] }
        if (i != null) {
            pos = pos + i - right.first + 1
        } else {
            // Сравнение левой части
            val match = left.reversed().all { j -> pattern[j] == text[pos + j] }
            if (match) result.add(pos)
            pos += q
        }
    }
    return result
}

Доказательство корректности и максимального количества сравнений аналогично доказательству первого варианта и также есть в [1].

Конечный двусторонний алгоритм использует оба предыдущих варианта, выбирая нужный в зависимости от того, является ли левая подстрока суффиксом периодической части правой. В алгоритме, кроме критического разбиения строки шаблона на ${u,v}$, где ${|u|<per(pattern)}$, также используется заранее вычисленный период только правой подстроки $v$. Его вычисление может быть произведено без дополнительных затрат одновременно с вычислением критического разбиения.

data class Factorization(
    val left: IntRange,
    val right: IntRange,
    val rightPeriod: Int
)

fun twoWay(text: String, pattern: String): List<Int> {
    // factorize() разбивает строку шаблона pattern на 2 подстроки:
    // left и right так, что |left| < per(pattern) и вычисляет период правой подстроки.
    // left, right — закрытые диапазоны индексов соответствующих подстрок.
    // rightPeriod — период правой подстроки
    val (left, right, rightPeriod) = factorize(pattern)

    // left — суффикс подстроки right[0..rightPeriod-1]
    val leftIsSuffixOfRight = left.all { i ->
        pattern[i] == pattern[right.first + rightPeriod - left.length + i]
    }
    return if (leftIsSuffixOfRight) {
        // rightPeriod равен периоду строки шаблона per(pattern).
        // Вызываем первый вариант алгоритма, используя left, right
        // и rightPeriod в качестве глобального периода
        cp1(text, pattern, left, right, rightPeriod)
    } else {
        // Вызываем второй вариант алгоритма, используя left, right
        // и q.
        val q = maxOf(left.length, right.length) + 1
        cp2(text, pattern, left, right, q)
    }
}

Доказательства корректности алгоритма, а также того, что ${q=max(|u|,|v|)+1}$ соответствует условию ${q≤per(pattern)}$ в случае, если $u$ не является суффиксом ${v[0…p-1]}$, даны в [1].

Алгоритм выполняется за время ${O(|text| + |pattern|)}$ с константной памятью, при этом выполняется не более ${2*|text|}$ сравнений.

Условие “${u\texttt{ — суффикс }v[0…p-1]}$” выполняется максимум за ${|pattern|/2}$ сравнений, вычисление периода и критического разбиения — ${4*|pattern|}$ сравнений, поэтому весь препроцессинг выполняется максимум за ${4.5*|pattern|}$ сравнений.

Пример работы алгоритма #

1. Возьмем шаблон ${pattern=\texttt{A}^n\texttt{B}}$. Критическое разбиение: ${(\texttt{A}^n, \texttt{B})}$. Поиск в тексте ${\texttt{B}^m}$ потребует ${2*|text|/|pattern|}$ сравнений. Несовпадение встречается в левой части, алгоритм сдвигает шаблон на 3 позиции.

2. Шаблон ${pattern=\texttt{A}^n\texttt{BA}^n}$ с глобальным периодом ${n+1}$. Критическое разбиение: ${(\texttt{A}^n, \texttt{BA}^n)}$. Левая часть — суффикс периодической части правой, поэтому будет использован первый вариант алгоритма и ${2*|text|-2e-2}$ сравнений при поиске в тексте ${text=(\texttt{A}^n\texttt{BA})^e\texttt{A}^{n-1}}$.

3. Шаблон ${pattern=\texttt{A}^n\texttt{BA}^{n-1}}$. Алгоритм будет использовать второй вариант и также выполнит ${2*|text|-2e-2}$ сравнений при поиске в тексте ${text=(\texttt{A}^n\texttt{BA})^e\texttt{A}^{n-1}}$.

Теорема о критическом разбиении #

Работа двустороннего алгоритма основывается на комбинаторных свойствах строки, обозначенных в теореме о критическом разбиении (Critical Factorization Theorem).

Теорема гласит, что любая строка $x$ имеет хотя бы одно критическое разбиение ${x=uv}$ (т.е. такое разбиение, что ${r(u,v)=per(x)}$). Более того, подстрока $u$ может быть выбрана такой, что ${|u|<per(x)}$.

Впервые она была сформулирована и доказана в работах Césari и Vincent в 1978, а в современном виде — в работе J. Duval (1989). Теорема имеет несколько доказательств, но для двустороннего алгоритма было представлено свое собственное, на основе вычисления максимальных суффиксов.

Введем отношения порядка строк.

Лексикографический (или алфавитный) порядок определяется на множестве строк ${A^{*}}$ упорядоченного алфавита $A$. Для двух строк ${x, y ∈ A^*}$ строка ${x≤y}$ тогда, когда выполняется одно из условий:

• $x$ — префикс $y$
• $x$ строго меньше $y$. Т. е. $x$ и $y$ можно представить как ${x=w\texttt{A}x, y=w\texttt{B}y}$, где ${w,x,y}$ — строки из множества ${A^{*}}$; а ${\texttt{A}, \texttt{B}}$ ­— два символа, такие, что ${\texttt{A}<\texttt{B}}$.

Обратный лексикографический порядок — лексикографический порядок на алфавите $A$, порядок символов которого заменен на обратный. Т.е. $x$ строго меньше $y$, если $x$ и $y$ можно представить как ${x=w\texttt{A}x, y=w\texttt{B}y}$, где ${w,x,y}$ — строки из множества ${A^{*}}$, а ${\texttt{A}, \texttt{B}}$ ­— два символа, такие, что ${\texttt{A}>\texttt{B}}$.

Обозначим через $≤$ прямой лексикографический порядок, а через $⪯$ — обратный.

Стоит отметить, что порядок $≤$ — не инверсия порядка $⪯$. Например, возьмем алфавит ${A=\\{\texttt{A},\texttt{B}\\}}$ с ${\texttt{A} < \texttt{B}}$. Для строк ${\tt ABB}$ и ${\tt ABBAA}$ верны оба равенства:

• ${\texttt{ABB} ≤ \texttt{ABBAA}}$
• ${\texttt{ABB} ⪯ \texttt{ABBAA}}$

Более того, в пересечении порядков $≤$ и $⪯$ совпадает только первое условие префикса. Т.е.оба выражения ${x ≤ y}$ и ${x ⪯ y}$ верны только в том случае, если $x$ — префикс $y$.

Ниже представлены все суффиксы строки ${\tt ABAABAA}$, отсортированные в прямом и обратном порядке:

  Суффиксы        ≤                ⪯
ABAABAA         A                BAA
BAABAA          AA               BAABAA
AABAA           AABAA            A
ABAA            ABAA             ABAA
BAA             ABAABAA          ABAABAA
AA              BAA              AA
A               BAABAA           AABAA

Максимальный суффикс — это наибольшая подстрока строки $x$ в соответствии с заданным лексикографическим порядком. Обозначим его через ${Maxsuf(x)}$. В примере выше ${Maxsuf(\tt ABAABAA)}$ равен ${\tt BAABAA}$ для прямого порядка и ${\tt AABAA}$ для обратного.

Теорема

Пусть $x$ ­ — непустая строка из символов алфавита $A$ и ${x=uv=u'v'}$, где $v$ ­— лексикографически максимальный суффикс строки $x$ в соответствии с прямым порядком ($≤$), а $v'$ — лексикографически максимальный суффикс $x$ в соответствии с обратным порядком (⪯). Если ${|v|≤|v'|}$, то ${uv}$ — критическое разбиение $x$, а иначе ${u'v'}$ — критическое разбиение $x$. Более того, ${|u|<per(x)}$ и ${|u'|<per(x)}$.

Доказательство дано в [1]

Имея эту теорему, задача нахождения критического разбиения сводится к задаче нахождения максимальных суффиксов для прямого и обратного алфавитного порядка.

Вычисление критического разбиения #

Ниже представлен алгоритм вычисления критического разбиения и максимальных суффиксов строки.

data class Factorization(
    val left: IntRange,
    val right: IntRange,
    val rightPeriod: Int
)

fun factorize(pattern: String): Factorization {
    val naturalOrder = computeMaxSuffixAndPeriod(pattern, naturalOrder())
    val reverseOrder = computeMaxSuffixAndPeriod(pattern, reverseOrder())
    return if (naturalOrder.right.length <= reverseOrder.right.length)
        naturalOrder else reverseOrder
}

fun computeMaxSuffixAndPeriod(pattern: String, 
                              comparator: Comparator<Char>): Factorization…

computeMaxSuffixAndPeriod() — функция, вычисляющая максимальный суффикс и период правой подстроки.

Пример 1

Шаблон ${pattern=\tt \underlinesegment{ABA}\underlinesegment{ABA}\underlinesegment{A\space\space\space}}$
Период ${pattern}$: ${p=3}$

Разбиение для прямого порядка — не критическое, его локальный период = 2 (${\texttt{BA}}$). Разбиение для обратного порядка — критическое.

Пример 2

Шаблон ${pattern=\tt \underlinesegment{ABABAABB}\underlinesegment{ABABA\space\space\space\space}}$
Период ${pattern}$: ${p=8}$

Оба разбиения критические.

Алгоритм вычисления максимального суффикса основан на использовании декомпозиции Линдона. Вместе с максимальным суффиксов в одном цикле вычисляется также период правой подстроки $v$.

fun computeMaxSuffixAndPeriod(pattern: String, comparator: Comparator<in Char>): Factorization {
    var maxSuffix = -1
    var j = 0
    var k = 1
    var period = 1
    while (j + k < pattern.length) {
        val a = pattern[j + k]
        val b = pattern[maxSuffix + k]
        val abOrder = comparator.compare(a, b)
        when {
            // a < b
            abOrder < 0 -> {
                j += k
                k = 1
                period = j - maxSuffix

            // a == b
            abOrder == 0 -> {
                if (k != period) {
                    k += 1
                } else {
                    j += period
                    k = 1
                }

            // a > b
            else ->  {
                maxSuffix = j
                j = maxSuffix + 1
                k = 1
                period = 1
            }
        }
    }
    return Factorization(0 .. maxSuffix,
        maxSuffix + 1 .. pattern.lastIndex,
        period
    )
}

Обозначим через ${Maxsuf(x)}$ максимальный суффикс строки $x$ в соответствии с алфавитным порядком.

Пусть ${Maxsuf(x)=f^eg}$, где:
$f$, $g$ — подстроки
${|f|=per(Maxsuf(x))}$ (длина $f$ — это период строки максимального суффикса)
$g$ — собственный префикс подстроки $f$;
$e$ — целое число $e>0$.
Введем обозначения: ${Per(x)=f; \space Rest(x)=g}$
Отметим, что ${Rest(x)}$ — это грань строки ${Maxsuf(x)}$ и ${Border(Maxsuf(x))=f^{e-1}g}$, даже при ${e=1}$.

Переменная maxSuffix в алгоритме — позиция перед первым символом рассматриваемой строки максимального суффикса.
period — период строки максимального суффикса, длина ${Per(x)}$.
j … j+k — подстрока в ${Maxsuf(x)}$ последнего встреченного вхождения ${Rest(x)}$ в подстроке максимального суффикса.

Алгоритм выполняется за время ${O(|pattern|)}$, при этом выполняется менее ${2*|pattern|}$ сравнений.

Рассмотрим на примере, как изменяется максимальный суффикс строки $x$ при добавлении в её конец символов $\texttt{A}, \texttt{B}\text{ и }\texttt{C}$.

Пусть ${x=\tt ABCBCBACBCBACBC}$. В соответствии с алфавитным порядком её максимальный суффикс равен ${Maxsuf(x)=\texttt{CBCBACBCBACBC}=(\texttt{CBCBA})²\texttt{CBC}}$.
Макс. суффикс для строки ${x\texttt{A}}$: ${\tt CBCBACBCBACBCA}$ = ${Maxsuf(x)\texttt{A}}$. Слово без границ.
Макс. суффикс для строки ${x\texttt{B}}$: ${\tt CBCBACBCBACBCB}$ = ${Maxsuf(x)\texttt{B}}$. У строки такой же период, как и у ${Maxsuf(x)}$.
Макс. суффикс для строки ${x\texttt{C}}$: ${\tt CC}$.

Доказательство корректности алгоритма основывается на следующей лемме.

Лемма

Возьмем строку $x$, символ $\tt A$ и символ ${\texttt{A'}}$ такой, что ${Rest(x)\texttt{A'}}$ — это префикс ${Maxsuf(x)}$. Тогда значения ${Maxsuf(x\texttt{A}), Per(x\texttt{A}), Rest(x\texttt{A})}$ будут равны следующим:

Условие	$\bf Maxsuf(x\texttt{A})$	$\bf Per(x\texttt{A})$	$\bf Rest(x\texttt{A})$
${\texttt{A} < \texttt{A'}}$	${Maxsuf(x)\texttt{A}}$	${Maxsuf(x)\texttt{A}}$	$ε$
${\texttt{A} = \texttt{A'}}$	${Maxsuf(x)\texttt{A}}$	${Per(x)}$	${Rest(x)\texttt{A}}$, либо $ε$
${\texttt{A} > \texttt{A'}}$	${Maxsuf(Rest(x)\texttt{A})}$	${Per(Rest(x)\texttt{A})}$	${Rest(Rest(x)\texttt{A})}$

Доказательство дано в [1].