我的问题是我有一个由大约七千个 512 位字符串组成的数据集，我正在寻找最有效的方法来将它们相互比较并识别 30+ 位的重复序列。
我考虑过使用蛮力，但我认为这似乎不是一个合适的解决方案。
有很多算法可以执行字符串匹配，但我不知道哪一个最适合我的问题
问问题
816 次
1 回答
3
如果您有大量字符串并希望找到所有这些字符串共有的长子字符串，您可能需要考虑为所有字符串构建通用后缀树。完成此操作后，您可以通过使用深度优先搜索遍历树并查找具有多个不同字符串的结束标记的子字符串来找到字符串的任何子集共有的所有子字符串。
由于广义后缀树的大小为 O(N)，其中 N 是所有不同子字符串的字符总数，并且后缀树可以在 O(N) 时间内构建，因此该操作的整体运行时间应该为 O(N)。
希望这可以帮助！
于 2013-08-09T19:47:56.367 回答