c++ - 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. 第二个是构建一个 longest common prefix array施工时间为 O(n)。但我认为我的实现时间为 O(n^2)

所以对于第一个，即排序

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

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

Answer 1

首先，关于您的两个声明:

1) I am sorting all the suffixes of the string using stl sort. This may at least a O(nlogn) in worst case. So here i am violating O(n) construction.

std::sort 的复杂性这里比 O(n log n) 更糟糕。原因是 O(n log n) 假设有 O(n log n) 次单独比较，并且每次比较都在 O(1) 时间内执行。后一种假设是错误的，因为您排序的是字符串，而不是原子项(如字符或整数)。

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

2) Second one is in constructing a longest common prefix array construction is given O(n).But i think my implementation in O(n^2)

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

接下来，关于您的问题:

If I use count sort I may decrease to O(n). If I use Count sort is it correct? Is my understanding is correct? Let me know if my understanding is wrong.

很遗憾，您的理解不正确。如果您可以在 O(1) 时间内访问要排序的每个项目的原子键，则计数排序仅是线性的。同样，这些项目是长度为 O(n) 个字符的字符串，因此这行不通。

And is there any way to find LCP in O(n) time?

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

DC 算法的引用资料是 Juha Kärkkäinen, Peter Sanders: Simple linear work suffix array construction, Automata, Languages and Programming计算机科学讲义，第 2719 卷，2003 年，第 943-955 页 (DOI 10.1007/3-540-45061-0_73)。 (但这并不是允许您在线性时间内完成此操作的唯一算法。)

您可能还想看看这篇 SO 帖子中提到的开源实现:What's the current state-of-the-art suffix array construction algorithm? .除了后缀数组构造之外，那里使用的许多算法还支持线性时间 LCP 数组构造(但并非那里的所有实现实际上都可能包含该实现；我不确定)。

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