高效的算法,用于搜索长度超过另一个文本内文本的14个字符的匹配子字符串

Question

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

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

例:

长文:ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT 和更长的时间

模式:ACGGTATTGAC AAAACCCCGGGGTTTTA TGTTCCCAG

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

如果可能的话,奖励将是在C++中使用char数组实现此方法的一种方法.

Answer 1

这是一个算法 - 我不确定它是否有名称.它需要一个"滚动哈希" - 一个(非加密)哈希函数,它具有给定序列哈希值的属性,AB...C计算序列的哈希值是有效的B...CD.

1. 计算序列的滚动散列pattern[0..14],pattern[1..15],pattern[2..16]...和存储每个索引pattern在哈希表中.

2. 计算滚动哈希haystack[0..14]并查看它是否在哈希表中.如果是,比较haystack[0..14]到pattern[pos..pos+14]这里pos从哈希表中被检索.

3. 从滚动哈希中haystack[0..14],有效地计算滚动哈希haystack[1..15]并查看它是否在哈希表中.重复直到你到达结尾haystack.

请注意,您的15个字符串只有2 ^30个可能的值,因此您的"哈希函数"可以是一个简单的映射到字符串的值,该字符串被视为15位base-4数字,可快速计算,具有滚动哈希属性并且是独一无二的

Answer 2

退后一步，我要实时编码：

void match_substring(const char *a, const char *b, int n) // n=15 in your case
{
    int alen = strlen(a); // I'll leave all the null-checking and buffer-overrun business as an exercise to the reader
    int blen = strlen(b);
    for (int i=0; i<alen; i++) {
        for (int j=0; j<blen; j++) {
            for (int k; (i+k<alen) && (j+k<blen) && a[i+k]==b[i+k]; k++);
            if (k >= n)
                printf("match from (%d:%d) for %d bytes\n", i, j, k);
        }
    }
}