c++ - 在另一个文本中搜索长度超过 14 个字符的匹配子字符串的高效算法

Question

我有一个很长的文本(大约 5 MB 文件大小)和另一个称为模式的文本(大约 2000 个字符)。

任务是从长文本中的 15 个字符或更长的基因组模式中找到匹配的部分。

例子:

长文本:ACGTACGTGTCAAAAACCCCGGGGTTTTAGTACCCGTAGGCGTAT 和更长的时间

图案:ACGGTATTGAC公司AAAACCCCGGGGTTTTATGTTCCCAG

我正在寻找一种高效(且易于理解和实现)的算法。

如果可能的话，奖金将是一种仅使用 C++ 中的字符数组来实现此功能的方法。

Answer 1

这是一种算法 - 我不确定它是否有名称。它需要一个“滚动散列”——一个(非加密的)散列函数，它具有给定序列 AB...C 散列的属性，计算序列的散列是有效的B...CD.

1. 计算序列 pattern[0..14]、pattern[1..15]、pattern[2. .16]... 并将每个索引存储在哈希表中的 pattern 中。

2. 计算haystack[0..14]的rolling hash，看看它是否在哈希表中。如果是，将 haystack[0..14] 与 pattern[pos..pos+14] 进行比较，其中 pos 是从哈希中检索的表。

3. 根据 haystack[0..14] 的滚动哈希，高效地计算 haystack[1..15] 的滚动哈希并查看它是否在哈希表中。重复直到到达 haystack 的尽头。

请注意，您的 15 个字符串只有 2³⁰ 个可能的值，因此您的“哈希函数”可以是一个简单的映射到被视为 15 位 base-4 数字的字符串的值，这计算速度快，具有滚动哈希属性并且是唯一的。