在大量字符串中找到长时间重复的子字符串

在大量字符串中找到长时间重复的子字符串

执行此 *** 作的有效方法是创建子字符串的索引，并对它们进行排序。这是O（n lg n）运算。

BWT压缩执行此步骤，因此这是一个很好理解的问题，并且存在基数和后缀（要求O（n））排序实现，因此使其尽可能高效。仍然需要很长时间，大文本可能要花费几秒钟。

如果你想使用的工具代码，C ++

std::stable_sort()

进行 多
优于

std::sort()

自然语言（和比C的要快得多

qsort()

，但出于不同的原因）。

然后访问每个项目以查看其与相邻项目的公共子串的长度为O（n）。