c++ - 在非常大的序列中找到相似的子序列

Question

想象序列是Pi

141592653589793238462643383279502884197....

Pi 存储在一个文本文件中。

我想在 Pi 中找到一个相似的子序列，例如相似度为 80%。

例如我想在Pi中定位33384，所以

14159265358979 32384 62643383279502884197....

位数约为百万。

我需要一种高效的算法来搜索这些相似性。

我应该使用数据库而不是文件吗？

任何想法表示赞赏。

编辑:

我找到了一些算法，我需要检查一下，我会告诉你结果。

顺便说一下，算法是 Knuth–Morris–Pratt

Answer 1

您可以通过 pi 序列提取 M 个字符(M - 搜索长度)子序列。然后将子序列与搜索字符串进行比较。

然后只是异或搜索和子序列。 XOR 后计数不为 0 字节。计数是差异的数量。将差异计数与搜索字符串长度进行比较可以得出差异百分比。

如果差异合适，你会得到相似的子串。

更新:

您将得到 N-M 倍的子序列，比较复杂度为 O(M)。 N为pi串长度，M为子串长度