我有一个集合S，通常包含 10-50 个长字符串。出于说明目的，假设每个字符串的长度范围在 1000 到 10000 个字符之间。
我想找到指定长度的字符串k（通常在 5 到 20 的范围内），它们是S. 这显然可以使用一种简单的方法来完成 - 枚举中的每个 k 长度子字符串S[0]并检查它们是否存在于S.
有没有更有效的方法来解决这个问题？据我所知，这个问题和最长公共子序列问题有一些相似之处，但我对 LCS 的理解是有限的，我不确定它如何适应我们将所需的公共子串长度绑定到的情况k，或者是否可以应用子序列技术来查找子串。
我会将每个长字符串视为重叠的短字符串的集合，因此 ABCDEFGHI 变为 ABCDE、BCDEF、CDEFG、DEFGH、EFGHI。您可以将每个短字符串表示为一对索引，一个指定长字符串，另一个指定该字符串中的起始偏移量（如果这让您觉得幼稚，请跳到末尾）。
然后我会将每个集合按升序排序。
现在，您可以通过合并索引的排序列表来找到前两个集合共有的短字符串，仅保留第一个集合中也存在于第二个集合中的那些。根据第三个集合检查此幸存者，依此类推，最后的幸存者对应于所有长字符串中存在的那些短字符串。
（或者，您可以在每个排序列表中维护一组指针，并重复查看每个指针是否都指向具有相同文本的短字符串，然后前进指向最小短字符串的指针）。
初始排序的时间为 O(n log n)，这占主导地位。在最坏的情况下 - 例如，当每个字符串都是 AAAAAAAA..AA 时 - 除此之外还有一个因子 k，因为所有字符串比较都会检查所有字符并花费时间 k。希望有一个聪明的方法可以解决这个问题，使用https://en.wikipedia.org/wiki/Suffix_array，它允许您在时间 O(n) 而不是 O(nk log n) 和https://en 中进行排序。 wikipedia.org/wiki/LCP_array，它应该允许您在比较来自不同后缀数组的子字符串时跳过一些字符。
再次考虑这一点，我认为连接所有有问题的字符串（用其中任何一个字符串中都没有的字符分隔）的常用后缀数组技巧在这里是有效的。如果查看生成的后缀数组的 LCP，您可以将其拆分为多个部分，在后缀之间的差异少于 k 个字符的点处进行拆分。现在，任何特定部分中的每个偏移量都以相同的 k 个字符开头。现在查看每个部分中的偏移量，并检查是否与每个可能的起始字符串至少有一个偏移量。如果是，则该 k 字符序列出现在所有起始字符串中，否则不会出现。（有后缀数组结构可以处理任意大的字母表，因此如果需要，您可以随时扩展字母表以生成不在任何字符串中的字符）。