想象序列是Pi
141592653589793238462643383279502884197....
Pi 存储在一个文本文件中。
我想在 Pi 中找到一个相似的子序列，例如相似度为 80%。
例如我想在Pi中定位33384，所以
14159265358979 32384 62643383279502884197....
位数约为百万。
我需要一种高效的算法来搜索这些相似性。
我应该使用数据库而不是文件吗？
任何想法表示赞赏。
编辑:
我找到了一些算法，我需要检查一下，我会告诉你结果。
顺便说一下，算法是 Knuth–Morris–Pratt
最佳答案
您可以通过 pi 序列提取 M 个字符(M - 搜索长度)子序列。然后将子序列与搜索字符串进行比较。
然后只是异或搜索和子序列。 XOR 后计数不为 0 字节。计数是差异的数量。将差异计数与搜索字符串长度进行比较可以得出差异百分比。
如果差异合适，你会得到相似的子串。
更新:
您将得到 N-M 倍的子序列，比较复杂度为 O(M)。 N为pi串长度，M为子串长度
关于c++ - 在非常大的序列中找到相似的子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24523424/