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

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

第一列(位置数组)是后缀数组中排序后缀的原始起点。我们将第二列称为 SuffixArray(我们不需要计算它，它只是为了可视化)。

现在，我们知道 LCP[i]= SuffixArray[i] 和 SuffixArray[i+1] 之间的最长公共(public)前缀的长度。例如联通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);

}

next smaller element in array

---