3 
#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？

4

2 回答 2

6

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

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 2 log n)。

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

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

接下来，关于您的问题：

如果我使用计数排序，我可能会减少到 O(n)。如果我使用计数排序是否正确？我的理解正确吗？让我知道我的理解是否错误。

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

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

是的。最近的后缀数组计算算法，包括 DC 算法（又名 Skew 算法），提供了计算 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 阵列构造。

于 2013-07-02T14:47:18.140 回答
0

jogojapan 已经全面回答了您的问题。只是提到一个优化的 cpp 实现，您可能想看看这里。

在这里发布代码以防 GitHub 出现故障。

const int N = 1000 * 100 + 5; //max string length

namespace Suffix{
    int sa[N], rank[N], lcp[N], gap, S;
    bool cmp(int x, int y) {
        if(rank[x] != rank[y])
            return rank[x] < rank[y];
        x += gap, y += gap;
        return (x < S && y < S)? rank[x] < rank[y]: x > y;
    }
    void Sa_build(const string &s) {
        S = s.size();
        int tmp[N] = {0};
        for(int i = 0;i < S;++i)
            rank[i] = s[i],
            sa[i] = i;
        for(gap = 1;;gap <<= 1) {
            sort(sa, sa + S, cmp);
            for(int i = 1;i < S;++i)
                tmp[i] = tmp[i - 1] + cmp(sa[i - 1], sa[i]);
            for(int i = 0;i < S;++i)
                rank[sa[i]] = tmp[i];
            if(tmp[S - 1] == S - 1)
                break;
        }
    }
    void Lcp_build() {
        for(int i = 0, k = 0;i < S;++i, --k)
            if(rank[i] != S - 1) {
                k = max(k, 0);
                while(s[i + k] == s[sa[rank[i] + 1] + k])
                    ++k;
                lcp[rank[i]] = k;
            }
            else
                k = 0;
    }
};
于 2020-11-19T05:31:11.273 回答