LCP: сколько общего у соседей по суффиксному массиву

Если ты посчитаешь LCP для kokos, найдёшь по нему число различных подстрок и объяснишь, почему алгоритм Касаи идёт по суффиксам в порядке текста, - листай до «Теперь сам».

Как думаешь, сколько пар придётся сравнить

В тексте из 10 000 символов надо найти самый длинный кусок, который встречается хотя бы дважды. Прямой путь - взять каждую пару позиций и посмотреть, на сколько символов совпадают куски, начинающиеся с них. Пар около пятидесяти миллионов.

Прежде чем читать дальше, подумай: суффиксный массив этого текста уже построен. Какие пары позиций ДОСТАТОЧНО сравнить, чтобы не пропустить самый длинный повтор?

На что это похоже

Открой словарь на любой странице. Слова с длинным общим началом стоят рядом: переход, переходить, переходный. Если ты ищешь два слова словаря с самым длинным общим началом, незачем сравнивать абажур с переходом - достаточно пройти по словарю сверху вниз и сравнить каждое слово со следующим.

Причина в сортировке. Между двумя словами с общим началом перех могут стоять только слова с тем же началом: любое другое слово оказалось бы либо выше обоих, либо ниже. Значит, общее начало двух далёких слов не длиннее, чем у любых двух соседей между ними. Самая длинная общность всегда достигается на соседях.

Механизм: массив общих начал

LCP (от английского «самое длинное общее начало») - массив той же длины, что суффиксный: lcp[i] равно числу первых символов, общих у суффиксов sa[i − 1] и sa[i]. У верхнего суффикса соседа нет, lcp[0] = 0.

место    sa    суффикс     lcp    общее начало с соседом сверху
  0       5    a            0     -
  1       3    ana          1     a
  2       1    anana        3     ana
  3       0    banana       0
  4       4    na           0
  5       2    nana         2     na

Что из этой таблицы читается сразу:

максимум lcp = 3, на месте 2        самый длинный повтор - ana (позиции 3 и 1)
сумма lcp = 6                       различных подстрок 6 · 7 / 2 − 6 = 15

Вторая строка требует объяснения. Суффикс длины d даёт d подстрок - все свои начала. Всего суффиксы дают 1 + 2 + … + n = n(n + 1) / 2 подстрок, но с повторами. Начало суффикса уже встречалось раньше ровно тогда, когда оно же является началом соседа сверху, - а таких начал lcp[i] штук. Вычитаем повторы - остаются различные.

Правило

Общее начало любых двух суффиксов равно минимуму LCP на отрезке массива между ними; поэтому самая длинная общность всегда достигается на соседях. Отсюда: самая длинная повторяющаяся подстрока имеет длину max lcp; различных подстрок n(n + 1) / 2 − Σ lcp (знак Σ - сумма по всем местам массива). Алгоритм Касаи считает LCP за линейное время, обходя суффиксы в порядке ТЕКСТА: если у суффикса i с его соседом сверху общих символов h, то у суффикса i + 1 со своим соседом их не меньше h − 1.

Разбор: алгоритм Касаи на banana

По определению LCP считается так: для каждой пары соседей сравнивать символы с начала. На тексте из одинаковых букв каждая пара совпадает почти на всю длину - это квадрат.

Наблюдение Касаи. Пусть суффикс i и его сосед сверху, суффикс j, совпадают на h символов. Отрежем у обоих первый символ: получатся суффиксы i + 1 и j + 1, и они совпадают на h − 1 символ. Суффикс j + 1 при этом стоит в массиве выше суффикса i + 1. Значит, сосед суффикса i + 1 сверху совпадает с ним не меньше чем на h − 1: он зажат между ними. Начинать сравнение с нуля не нужно. При h = 0 гарантировать нечего, и сравнение честно идёт с начала - за этим в коде проверка if h > 0.

def kasai(t, sa):
    n = len(t)
    mesto = [0] * n                   # mesto[i] - на каком месте массива стоит суффикс i
    i = 0
    while i < n:
        mesto[sa[i]] = i
        i = i + 1
    lcp = [0] * n
    h = 0
    sravn = 0
    i = 0
    while i < n:                      # суффиксы в порядке текста
        if mesto[i] > 0:
            j = sa[mesto[i] - 1]      # сосед сверху
            while i + h < n and j + h < n:
                sravn = sravn + 1
                if t[i + h] != t[j + h]:
                    break
                h = h + 1
            lcp[mesto[i]] = h
            if h > 0:
                h = h - 1             # следующему суффиксу гарантировано h - 1
        else:
            h = 0                     # у верхнего суффикса соседа нет
        i = i + 1
    return [lcp, sravn]

Проход по banana, sa = [5, 3, 1, 0, 4, 2]:

i   суффикс   место   сосед сверху    h на входе   сравнения            lcp    h на выходе
0   banana      3     anana (1)           0        b ≠ a                 0         0
1   anana       2     ana (3)             0        a = a, n = n, a = a   3         2
2   nana        5     na (4)              2        нет: сосед кончился   2         1
3   ana         1     a (5)               1        нет: сосед кончился   1         0
4   na          4     banana (0)          0        n ≠ b                 0         0
5   a           0     нет                 -        -                     -         0

Пять сравнений на весь массив. Строки i = 2 и i = 3 получили свои значения готовыми: два и один символ гарантированы предыдущим шагом, а продлевать некуда.

Разбор: три вопроса без поиска и замер

Текст t = tekst(10000, 4, 1) из прошлого урока, суффиксный массив построен.

Первый вопрос - самый длинный повтор. Максимум LCP равен 11: кусок aaadcbbaabb стоит в тексте с позиций 1988 и 9412. Ответ на вопрос из начала урока: сравнить достаточно n − 1 пару соседей по массиву, а не пятьдесят миллионов пар.

Второй - число различных подстрок. Всего подстрок 10000 · 10001 / 2 = 50 005 000, сумма LCP 58 255, различных 49 946 745. Почти все подстроки случайного текста различны; повторяются только короткие.

Третий - наибольшая общая подстрока двух строк. Склеиваем их через символы, которых нет ни в одной: a + "#" + b + "$". Строим массив и LCP для склейки и ищем максимум LCP среди соседей, из которых один суффикс начинается в первой строке, а другой - во второй. Суффикс начинается в первой строке, если его начало sa[i] меньше длины a. Суффиксы, начинающиеся с разделителей, в максимум не попадают: их общее начало с соседями равно нулю.

banana  и  ananas      →   anana   (5 символов)
kolobok и  kolokol     →   kolo    (4 символа)

Динамическое программирование из раздела 15 решает ту же задачу таблицей n × m; здесь цена - построение массива по склейке.

Теперь цена самого LCP, в сравнениях символов:

текст                    по определению     Касаи
tekst(10000, 4, 1)           68 248         19 989
"a" * 1000                  499 500            999
"ab" * 500                  498 502            999

«По определению» - это та же программа, в которой перед каждым сравнением стоит h = 0.

На случайном тексте общие начала короткие, и счёт по определению терпим. На повторах он квадратичен, а Касаи остаётся под 2n: h растёт только при успешном сравнении, убывает не больше чем на единицу за шаг, и выше n подняться не может.

Что ломается без этого

Первое: h = 0 вместо h − 1. Каждое сравнение начинается с нуля. Ответ останется верным, а цена вернётся к квадрату: на тысяче букв a - полмиллиона сравнений. Ни один тест на правильность этого не покажет.

Второе: обход в порядке массива. Если перебирать суффиксы по местам массива, а не по позициям текста, гарантия h − 1 не действует: соседние места массива - это не «тот же суффикс без первого символа». Значение, оставшееся от прошлого шага, окажется больше настоящего, и LCP выйдет завышенным.

Третье: склейка без разделителей. Строки xa и bxab склеены как xabxab. Суффиксы с позиций 0 и 3 совпадают на три символа - xab, - и один из них начинается в первой строке, другой во второй. Но в первой строке всего два символа: «общая подстрока» перешагнула через стык. Разделители обязаны быть чужими для обеих строк и разными: с одинаковыми склейка x#x# даёт суффиксам x#x# и x# общее начало x# длиной два, хотя общая подстрока - один символ.

Четвёртое: максимум по всем соседям при поиске общей подстроки. Если не проверять, что соседи из РАЗНЫХ строк, найдётся повтор внутри одной строки: для banana и xyz ответом станет ana.

Пятое: сдвиг индекса. В одних книгах lcp[i] - общее начало с соседом СВЕРХУ, в других - СНИЗУ. Формулы те же, индексы сдвинуты на единицу. Смешать две договорённости в одной программе - самый частый источник ошибок на единицу в этой теме.

Зачем это в работе

Первый сюжет - поиск дублей. Найти в кодовой базе куски длиннее сорока символов, повторённые дважды и больше, - это все места массива, где LCP не меньше сорока. Так работают детекторы копирования кода и поиск заимствований в текстах.

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

Третий - ускорение самого поиска. С таблицей LCP и структурой для минимума на отрезке (разреженная таблица из раздела про деревья) общее начало ЛЮБЫХ двух суффиксов получается за одно действие. На этом построены поиск образца за m + log n вместо m · log n и десятки задач про палиндромы, повторы и периоды.

Теперь сам

Суффиксный массив слова kokos - [0, 2, 1, 3, 4]. Посчитай LCP. Какая подстрока повторяется и сколько в слове различных подстрок?

место    sa    суффикс    lcp    общее начало с соседом сверху
  0       0    kokos       0     -
  1       2    kos         2     ko
  2       1    okos        0
  3       3    os          1     o
  4       4    s           0