使用后缀数组和LCP快速查找文本中的子串

Question

我正在尝试在一段很大的文本中找到包含某个子字符串的单词。这个文本看起来像这样：*america*python*erica*escape*..

举个例子：输入是“rica”，那么输出就是：america, erica

我使用了后缀数组。

我的伪代码（类似Python的写法）是：

firstChar=input[0] // the first character of input
suffixArray=getSuffixArray(text) // suffix array
result=[]

for every index of suffix array which points to firstChar:
    length=len(input)
    indexText=text[suffixArray[index]]
    indexes=[]

    if input in text[indexText: indexText+length]:
        word=find whole word containig this index between '*' 
        result.append(word)

这个方法可以工作，但速度太慢了。LCP数组应该能提高算法的运行速度，但我不知道该怎么做。你能给我一些建议吗？

提前谢谢你！

Answer 1

在这里有一段免费的Python代码，可以用来生成后缀数组，链接在这里：高效查找最长重复字符串的方法。这段代码在个人电脑上可以处理多达1亿个字符。