Как LCP помогает найти количество вхождений шаблона?

Я прочитал, что Самый длинный общий префикс (LCP) можно использовать для поиска числа вхождений шаблона в строке.

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

Хотя использование двоичного поиска для поиска количества вхождений шаблона очевидно, я не могу понять, как LCP помогает найти количество вхождений здесь.

Например, для этого массива суффиксов для banana:

Как помочь LCP найти количество вхождений подстроки типа "банан" или "na", не очевидно для меня.

Любая помощь в определении того, как LCP помогает здесь?

Ответы

Ответ 1

Я не знаю, как использовать LCP-массив вместо выполнения двоичного поиска, но я считаю, что вы называете технику, описанную Уди Манбером и Джином Майерсом в Суффиксные массивы: новый метод для поиска в строке строки в строке.

Идея такова: для того, чтобы найти количество вхождений данной строки P (длина m) в тексте T (длина N),

Вы используете двоичный поиск с массивом суффиксов T (как и вы предполагали)
Но вы ускорите его, используя массив LCP в качестве вспомогательной структуры данных. Более конкретно, вы создаете специальную версию массива LCP (я буду называть его LCP-LR ниже) и используйте это.

Проблема с использованием стандартного двоичного поиска (без информации LCP) заключается в том, что в каждой из сопоставлений O (log N) вам нужно сделать, вы сравниваете P с текущей записью суффикса array, что означает полное сравнение строк до m символов. Таким образом, сложность O (m * log N).

Массив LCP-LR помогает улучшить это до O (m + log N) следующим образом:

В любой момент в алгоритме бинарного поиска вы рассматриваете, как обычно, диапазон (L,..., R) массива суффиксов и его центральную точку M и решаете, продолжаете ли вы поиск в левой части -range (L,..., M) или в правом поддиапазоне (M,..., R).
Чтобы принять решение, вы сравниваете P с строкой в M. Если P идентично M, вы закончите, но если нет, вы сравните первые k символов P и затем решите, будет ли P лексикографически меньше или больше M. Предположим, что результатом является то, что P больше, чем M.
Итак, в следующем шаге вы рассматриваете (M,..., R) и новую центральную точку M 'в середине:
```
              M ...... M' ...... R
              |
       we know:
          lcp(P,M)==k
```
Теперь трюк состоит в том, что LCP-LR предварительно вычисляется так, что O (1) -lookup сообщает вам самый длинный общий префикс M и M ', lcp (M, M').

Вы уже знаете (с предыдущего шага), что сам M имеет префикс из k символов, общих с P: lcp (P, M) = k. Теперь есть три возможности:
- Случай 1: k < Icp (M, M '), то есть P имеет меньше префиксных символов, общих с M, чем M имеет общее с M'. Это означает, что (k + 1) -й символ M 'такой же, как у M, а так как P лексикографически больше M, он должен лексикографически больше, чем M'. Итак, мы продолжаем в правой половине (M ',..., R).
- Случай 2: k > lcp (M, M '), то есть P имеет больше префиксных символов, общих с M, чем M имеет общее с M'. Следовательно, если бы мы сравнивали P с M ', общий префикс был бы меньше k, а M' был бы лексикографически больше, чем P, поэтому, фактически не проведя сравнения, мы продолжим в левой половине (M,...., М ').
- Случай 3: k == lcp (M, M '). Таким образом, M и M 'идентичны с P в первых k символах. Чтобы решить, продолжаемся ли мы в левой или правой половине, достаточно сравнить P с M ', начиная с (k + 1) -го символа.
Мы продолжаем рекурсивно.

Общий эффект заключается в том, что ни один символ P не сравнивается с каким-либо символом текста более одного раза. Общее количество сравнений символов ограничено m, поэтому общая сложность действительно равна O (m + log N).

Очевидно, что оставшийся ключ вопроса заключается в том, как мы прекомпилировали LCP-LR, чтобы он мог рассказать нам в O (1) время lcp между любыми двумя элементами массива суффикса? Как вы сказали, стандартный массив LCP сообщает вам только lcp последовательных записей, то есть lcp (x-1, x) для любого x. Но M и M 'в описании выше не обязательно являются последовательными записями, так как это делается?

Ключом к этому является осознание того, что во время бинарного поиска будут встречаться только определенные диапазоны (L,..., R): он всегда начинается с (0,..., N) и делит это в центре, а затем продолжается либо влево, либо вправо и снова разделяет эту половину и так далее. Если вы думаете об этом: каждая запись массива суффиксов встречается как центральная точка только одного возможного диапазона во двоичном поиске. Таким образом, существует ровно N различных диапазонов (L... M... R), которые могут играть роль во двоичном поиске, и достаточно прекомпутировать lcp (L, M) и lcp (M, R) для тех N возможных диапазоны. Таким образом, это 2 * N различных заранее вычисленных значений, поэтому LCP-LR имеет размер O (N).

Кроме того, существует прямой рекурсивный алгоритм для вычисления значений 2 * N LCP-LR в O (N) времени из стандартного массива LCP – Я бы предложил опубликовать отдельный вопрос, если вам нужно подробное описание этого.

Подводя итог:

Можно вычислить LCP-LR в O (N) время и O (2 * N) = O (N) пространство из LCP
Использование LCP-LR во время двоичного поиска помогает ускорить процедуру поиска от O (M * log N) до O (M + log N)
Как вы предположили, вы можете использовать два бинарных поиска для определения левого и правого конца диапазона соответствия для P, а длина диапазона соответствия соответствует количеству вхождений для P.

Ответ 2

Самый длинный общий префикс (LCP) является самым низким общим предком (LCA) в дереве суффиксов. Как только у вас есть младший общий предок, вы можете подсчитать количество узлов, которые выходят из LCA. Это даст вам количество вхождений шаблона в дереве суффиксов. Это связь между LCP и LCA.