Быстрый способ найти подстроку в тексте, используя суффикс массив и lcp

Question

Я пытаюсь найти слова, которые содержат подстроку (в качестве входных данных) в большом тексте. Текст выглядит так: * америка * питон * эрика * escape *.. Пример: ввод: "рика" => вывод: америка, эрика

Я использую массив суффиксов.

Мой псевдокод (похожий на питон):

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 для массива суффиксов - это эффективный способ найти самую длинную повторяющуюся строку. Он работает до 100 миллионов символов на персональном компьютере.