Как я могу найти номер вхождения каждого суффикса в строке?

Suffix Array Solution

Построить дерево суффиксов строки S вместе с массивом LCP. Это поможет подсчитать все вхождения каждого суффикса.

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

массив суффиксов

LCP

алгоритм Касая для построения массива LCP из суффиксного массива

Давайте возьмем пример строки и создадим ее суффиксный массив. Рассмотрим строку S = «ABABBAABB».

suffix positions(pos)   Suffixes of S   LCP array of S
5                   AABB            1
0                   ABABBAABB       2
6                   ABB             3
2                   ABBAABB         0
8                   B               1
4                   BAABB           2
1                   BABBAABB        1
3                   BBAABB          2
7                   BB              not Defined

Первый столбец (массив pos) — исходные отправные точки отсортированных суффиксов в массиве суффиксов. Позвольте назвать второй столбец как суффиксный массив (нам не нужно вычислять это, это просто для визуализации).

Теперь, как мы знаем, LCP [i] = длина самого длинного общего префикса между SuffixArray [i] и SuffixArray [i + 1]. например LCP1= LCP ( «ABABBAABB», «АББ») = 2.

Пусть Count [i] = количество вхождений суффикса, начиная с позиции i.

for (int i = 0; i < n; )
{
int j=i;
while(LCP[j]==n-pos[j]){ // loop if SuffixArray[j] is a prefix of SuffixArray[j+1]
j++;
}
int incr=1;
for (int k = j-1; k>= i ; --k)
{
count[ pos[k] ] = incr;
incr++;
}
i=j+1;
}

Это высоко оптимизированное решение, и если вы внимательно посмотрите на все этапы, сложность O (n log n).

Надеюсь, поможет. Пожалуйста, пройдите все заново, если вы не поняли с первой попытки.

РЕДАКТИРОВАТЬ: В этом вычислении массива count есть небольшая ошибка. В основном моя проблема заключается в том, чтобы найти ближайший следующий индекс в массиве LCP, который меньше текущего значения. Я предоставляю правильную реализацию.

stack< int > stack;

count[ pos[n-1] ] = 1;

for(int i=n-2;i>=0;i--){
while(!stack.empty() and LCP[stack.top()]>=LCS[i]){
stack.pop();
}

if( LCP[i] == n-pos[i]  ){
if (stack.empty())
{
count[ pos[i] ] = n-i ;
}else{
count[ pos[i] ] = stack.top()-i ;
}

}else{
count[ pos[i] ] = 1;
}

stack.push(i);

}

следующий меньший элемент в массиве