标签: suffix-array

我根本找不到任何好的教学资源来解释后缀数组.甚至"圣经"也没有涵盖它.

我在哪里可以找到后缀数组及其用途的清晰而全面的解释？(视频课程很理想,因为我很懒.)

我需要找到n个字符串中最长的公共子字符串,并在我的项目中使用结果.

java中是否有现有的实现/库已经这样做了？

感谢您提前回复.

我正在尝试完成 Coursera 上的字符串算法课程，并且坚持使用此视频中描述的构建 LCP 数组的方法：

https://www.coursera.org/learn/algorithms-on-strings/lecture/HyUlH/computing-the-lcp-array

我很难理解这个视频中提出的理论。根据我自己的研究（谷歌搜索），我认为他们所描述的是 Kasai 的算法。但就像视频一样，所有的解释都使用非常抽象的解释或大量的代码样本。在不了解理论的情况下，我发现代码示例难以理解。我只是想用真实世界的例子来寻找解释。

即： S=ababaa$ 使用 Kasai 算法产生最终 LCP 数组的步骤是什么。

后缀数组将索引给定字符串列表的所有后缀,但如果您尝试索引所有可能的唯一子字符串,该怎么办？我对此有点新意,所以这是我的意思的一个例子:

鉴于字符串

abcd

后缀数组索引(至少根据我的理解)

(abcd,bcd,cd,d)

我想索引(所有子串)

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

我正在寻找一个后缀数组？如果是这样,我该怎么做才能将所有子字符串编入索引？如果没有,我应该在哪里看？还有什么我会谷歌对比"所有子串"与"后缀子串"？

有人可以解释这个从后缀数组构建LCP的代码是如何工作的吗？suffixArr[]是一个数组,用于suffixArr[i]保存带有等级i的后缀的字符串中的索引值.

 void LCPconstruct()
{
    int i,C[1001],l;
    C[suffixArr[0]] = n;


    for(i=1;i<n;i++)
    C[suffixArr[i]] = suffixArr[i-1];

    l = 0;

   for(i=0;i<n;i++)
   {
    if(C[i]==n)
        LCPadj[i] = 0;
    else
    {
        while(i+l<n && C[i]+l<n && s[i+l] == s[C[i]+l])
            l++;
        LCPadj[i] = l;

        l = max(l-1,0);
    }
  }

  for(i=0;i<n;i++)
     cout<<LCPadj[suffixArr[i]]<<"\n";


}

#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); …

我知道后缀数组本身的定义是它是一个字符串所有后缀的排序数组.但我试图了解这种排序操作的重要性在这里？假设我们创建了一个包含字符串所有后缀的数组,并选择不对其进行排序并继续构建LCP数组,当我们尝试解决诸如Longest Palindromic子字符串之类的常见问题时,我们在这种情况下会松动什么呢？最长的重复子串？

我想编写一个输出后缀数组的函数。这是我到目前为止所拥有的：

def suffixArray(s):
    sa = []
    for i in range(len(s)):
        suffix= sorted([s[i:]])
        sa = [len(s)-len(suffix[i:])
    return list(sa)

这会输出一个错误，因为我认为我缺少一个附加的 if 语句，但我不太确定如何处理它。是的，我知道可能有更简单的方法来获取后缀数组，但我是 python 的初学者，我可以使用的函数很少。任何帮助表示赞赏。谢谢

这也是我希望输入和输出的示例： 输入 --> suffixArray('banana') 输出 --> [5, 3, 1, 0, 4, 2]

要在n个字符的字符串上构建一个suffis数组,

1. 我们首先生成n个后缀O(n)
2. 然后对它们进行排序O(n log n)

总时间复杂度显示为O(n)+ O(nlogn)= O(nlogn).

但我正在读它是O(n ^ 2 log n)并且无法理解如何.有人可以解释一下吗？