如何找到字符串中每个后缀的出现次数？

Question

我想在 O(nlogn) 或 O(n) 时间内找出字符串的每个后缀在原始字符串中出现了多少次。

例如字符串aba，后缀a出现两次，ba出现一次，aba出现一次。

Answer 1

后缀数组解法

构造字符串S的后缀树和LCP数组。这将有助于计算每个后缀的所有出现次数。

不了解什么是后缀数组和LCP，很难理解。

suffix array

LCP

kasai’s Algorithm for Construction of LCP array from Suffix Array

让我们以字符串为例并创建其后缀数组。考虑字符串 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] 之间的最长公共前缀的长度。例如LCP1=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);

}

next smaller element in array

如何找到字符串中每个后缀的出现次数？

How can I find the occurence number of each suffix in a string?

c++

string

algorithm

hash

suffix-array