Как найти i-ю подстроку строки с использованием массива суффикса и массива LCP?

Question

Если расположить все различные подстроки из строки лексикографически и нам нужен i-й подстроки

1.) Можно ли найти его, используя его suffix array и LCP array?

2.) Если да, то как мы это сделаем? это можно сделать в O (Nlog^N) при создании массива суффиксов с использованием Manber & Myers, который имеет временную сложность O (Nlog^2N) или при создании его массива LCP с использованием алгоритма kasai, который имеет временную сложность O (N)?

Answer 1

Да, это может быть сделано с использованием массива суффикса и массива LCP.

Предполагая, что вы знаете, как вычислить массив суффикса и массив LCP.

Let p[] обозначают суффикс-массив lcp[] обозначают массив LCP.

создать массив, в котором хранится количество отдельных подстрок до i'th ранг суффикса. Это можно вычислить по этой формуле. Для получения дополнительной информации см Here

Пусть cum[] обозначают кумулятивный массив, который может быть рассчитан следующим образом:

cum[0] = n - p[0]; 
for i = 1 to n do: 
    cum[i] = cum[i-1] + (n - p[i] - lcp[i]) 

Теперь для поиска i'th подстроки просто найти нижнюю грань i в совокупном массиве cum[] что даст вам ранг суффикса, с которого должна начинаться ваша подстрока, и печатать весь символ до длины

i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
          // length of sub string starting from cum[pos-1] we should 
          // subtract cum[pos-1] from i and add lcp[pos] as it is 
          // common string between current rank suffix and 
          // previous rank suffix. 

, где pos - значение возврата по нижней границе.

Весь вышеописанный процесс можно суммировать следующим образом:

string ithSubstring(int i){ 
    pos = lower_bound(cum , cum + n , i); 
    return S.substr(arr[pos] , i - cum[pos-1] + lcp[pos]);// considering S as original character string 
} 

Для полной реализации суффикса массива, LCP и выше логики вы можете увидеть Here