C++中后缀数组的实现

Question

#include<iostream>
#include<string.h>
#include<utility>
#include<algorithm>

using namespace std;

struct xx
{
    string x;
    short int d;
    int lcp;
};

bool compare(const xx a,const xx b)
{
    return a.x<b.x;
}

int findlcp(string a,string b)
{
    int i=0,j=0,k=0;
    while(i<a.length() && j<b.length())
    {
        if(a[i]==b[j])
        {
            k++;
            i++;
            j++;
        }
        else
        {
            break;
        }
    }
    return k;
}

int main()
{   
    string a="banana";
    xx b[100];
    a=a+'$';
    int len=a.length();
    for(int i=0;i<len;i++)
    {
        b[i].x=a.substr(i);
        b[i].d=i+1;
    }
    sort(b,b+len,compare);
    for(int i=0;i<len;i++)
        cout<<b[i].x<<" "<<b[i].d<<endl;
    b[0].lcp=0;
    b[1].lcp=0;
    for(int i=2;i<len;i++)
    {
        b[i].lcp=findlcp(b[i].x,b[i-1].x);
    }
    for(int i=0;i<len;i++)
        cout<<b[i].d<<" "<<b[i].lcp<<endl;      
}

这是Suffix Array的实现 。在最坏的情况下，我在维基百科文章结构中的问题是 o(n)

所以在我的建设中：

1. 我正在使用 stl sort 对字符串的所有后缀进行排序。在最坏的情况下，这可能至少是 O(nlogn)。所以在这里我违反了 O(n) 构造。
2. 第二个是在构造最长的公共前缀数组构造中给出 O(n)。但我认为我在 O(n^2) 中的实现

所以对于第一个即排序

• 如果我使用计数排序，我可能会减少到 O(n)。如果我使用计数排序是否正确？我的理解是否正确？如果我的理解有误，请告诉我

• 有没有办法在 O(n) 时间内找到 LCP？

Answer 1

首先，关于你的两个陈述：

1) 我正在使用 stl sort 对字符串的所有后缀进行排序。在最坏的情况下，这可能至少为 O(nlogn)。所以在这里我违反了 O(n) 构造。

std::sort这里的复杂度比 O(n log n) 差。原因是 O(n log n) 假设有 O(n log n) 个单独的比较，并且每个比较都在 O(1) 时间内执行。后一个假设是错误的，因为您正在对字符串进行排序，而不是对原子项（如字符或整数）进行排序。

由于作为主字符串的子字符串的字符串项的长度是 O(n)，可以肯定地说排序算法的最坏情况复杂度是 O(n ² log n)。

2）第二个是在构造一个最长的公共前缀数组时给出 O(n)。但我认为我在 O(n^2) 中的实现

是的，您的 LCP 数组的构造是 O(n ² ) 因为您正在运行lcp函数 n ==len次，并且您的lcp函数需要 O(min(len(x),len(y))) 时间来处理一对字符串x，y。

接下来，关于你的问题：

如果我使用计数排序，我可能会减少到 O(n)。如果我使用计数排序是否正确？我的理解是否正确？如果我的理解有误，请告诉我。

不幸的是，您的理解是错误的。如果您可以在 O(1) 时间内访问要排序的每个项目的原子键，则计数排序只是线性的。同样，这些项目的长度是字符串 O(n) 个字符，所以这不起作用。

有没有办法在 O(n) 时间内找到 LCP？

是的。最近的后缀数组计算算法，包括 DC 算法（又名偏斜算法），提供了计算 LCP 数组和后缀数组的方法，并且在 O(n) 时间内完成。

DC 算法的参考资料是 Juha Kärkkäinen, Peter Sanders: Simple linear work suffix array construction, Automata, Languages and Programming Lecture Notes in Computer Science Volume 2719, 2003, pp 943-955 (DOI 10.1007/3-540-45061-0_73 ）。（但这并不是唯一允许您在线性时间内执行此操作的算法。）

您可能还想看看这篇 SO 帖子中提到的开源实现：当前最先进的后缀数组构造算法是什么？. 除了后缀数组构造之外，那里使用的许多算法还支持线性时间 LCP 数组构造（但并非所有实现都可能实际包含该实现；我不确定）。

如果您对 Java 中的示例没问题，您可能还想查看jSuffixArrays的代码。除其他算法外，它包括 DC 算法的实现以及线性时间的 LCP 阵列构造。