我有一个很长的文本(大约 5 MB 文件大小)和另一个称为模式的文本(大约 2000 个字符)。
任务是从长文本中的 15 个字符或更长的基因组模式中找到匹配的部分。
例子:
长文本: ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT 和更长的时间
图案: ACGGTATTGAC公司 AAAACCCCGGGGTTTTA TGTTCCCAG
我正在寻找一种高效(且易于理解和实现)的算法。
如果可能的话,奖金将是一种仅使用 C++ 中的字符数组来实现此功能的方法。
最佳答案
这是一种算法 - 我不确定它是否有名称。它需要一个“滚动散列”——一个(非加密的)散列函数,它具有给定序列 AB...C
散列的属性,计算序列的散列是有效的B...CD
.
计算序列
pattern[0..14]
、pattern[1..15]
、pattern[2. .16]
... 并将每个索引存储在哈希表中的pattern
中。计算
haystack[0..14]
的rolling hash,看看它是否在哈希表中。如果是,将haystack[0..14]
与pattern[pos..pos+14]
进行比较,其中pos
是从哈希中检索的表。根据
haystack[0..14]
的滚动哈希,高效地计算haystack[1..15]
的滚动哈希并查看它是否在哈希表中。重复直到到达haystack
的尽头。
请注意,您的 15 个字符串只有 230 个可能的值,因此您的“哈希函数”可以是一个简单的映射到被视为 15 位 base-4 数字的字符串的值,这计算速度快,具有滚动哈希属性并且是唯一的。
关于c++ - 在另一个文本中搜索长度超过 14 个字符的匹配子字符串的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10490963/