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

Question

Я хочу узнать, сколько раз каждый суффикс строки встречается в исходной строке за O(nlogn) или O(n) время.

Например, для строки aba суффикс a появляется дважды, ba появляется один раз, aba появляется один раз.

Answer 1

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) - это исходные начальные точки отсортированных суффиксов в массиве суффиксов. Пусть второй столбец называется SuffixArray (нам не нужно его вычислять, он только для визуализации).

Теперь, как мы знаем, LCP[i]= длина самого длинного общего префикса между SuffixArray[i] и SuffixArray[i+1]. например, LCP 1= lcp ("ABABBAABB", "ABB") = 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).

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

---

РЕДАКТИРОВАТЬ: есть небольшая ошибка в этом вычислении массива подсчета. В основном моя проблема заключается в том, чтобы найти ближайший следующий индекс в массиве 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);

}

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

---