我有一个集合 S
,通常包含10-50个长字符串。为了说明问题,假设每个字符串的长度在1000到10000个字符之间。
我想找到特定长度 k
的字符串(通常在5到20的范围内),它们是S
中每个字符串的子字符串。这显然可以使用朴素方法完成 - 枚举S[0]
中的每个k长度子字符串,并检查它们是否存在于S
的每个其他元素中。
是否有更有效的方法来解决这个问题?据我所知,这与最长公共子序列问题有一些相似之处,但我对LCS的理解有限,不确定如何将其调整为我们将期望公共子字符串长度限制为k
的情况,或者是否可以应用子序列技术来查找子字符串。