Максимальная пара

В информатике максимальная пара внутри строки — это пара совпадающих подстрок, которые являются максимальными, где «максимальный» означает, что невозможно создать более длинную совпадающую пару, расширив диапазон обеих подстрок влево или вправо.

Пример

Индекс	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Характер	х	а	б	с	и	а	б	с	В	а	б	с	и	С

Например, в этой таблице подстроки с индексами 2–4 (красным цветом) и индексами 6–8 (синим цветом) являются максимальной парой, поскольку содержат одинаковые символы ( abc), и слева от них стоят разные символы ( x по индексу 1 и y под индексом 5) и разные символы справа ( y под индексом 5 и w под индексом 9). Аналогично, подстроки с индексами 6–8 (синим цветом) и индексами с 10 по 12 (зеленым цветом) представляют собой максимальную пару.

Однако подстроки с индексами 2–4 (красным цветом) и индексами 10–12 (зеленым цветом) не являются максимальной парой, поскольку символ y следует за обеими подстроками, поэтому их можно расширить вправо, чтобы создать более длинную пару.

Формальное определение

Формально максимальная пара подстрок с начальными позициями $p_{1}$ и $p_{2}$ соответственно, и обе длины $l$ , определяется тройкой $(p_{1},p_{2},l)$ , такой, что для заданной строки $S$ длины $n$ , $S[p_{1}..p_{1}+l-1]=S[p_{2}..p_{2}+l-1]$ (это означает, что подстроки имеют идентичное содержимое), но $S[p_{1}-1]\neq S[p_{2}-1]$ (слева от них разные символы) и $S[p_{1}+l]\neq S[p_{2}+l]$ (они также имеют разные символы справа; вместе эти два неравенства являются условием максимальности). Таким образом, в приведенном выше примере максимальными парами являются $(2,6,3)$ (красная и синяя подстроки) и $(6,10,3)$ (зеленая и синяя подстроки) и $(2,10,3)$ не является максимальной парой.

Связанные понятия и временная сложность

Максимальный повтор — это строка, представленная максимальной парой. Супермаксимальный повтор — это максимальный повтор, который никогда не встречается как подстрока другого максимального повтора. В приведенном выше примере abc и abcy оба являются максимальными повторами, но только abcy это сверхмаксимальный повтор.

Максимальные пары, максимальные повторы и супермаксимальные повторы можно найти в $\Theta (n+z)$ время с использованием суффиксного дерева , ^[1] если есть $z$ такие структуры.