与一个或零不匹配匹配的字符串模式

Question

给定一个字符串和一个匹配的模式,找到匹配的效率有多为零或一个不匹配.

e.g) 
S = abbbaaabbbabab
P = abab

Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)

我试图修改KMP算法,但我不确定这种方法.

请让我知道继续解决问题.

谢谢.

Answer 1

好的我找到了!我找到了最好的算法!

这可能听起来有点勇敢,但只要我要提出的算法同时具有运行时间O(m + n)和内存消耗O(m + n),并且条目数据本身具有相同的属性,则算法可以仅在常量中进行优化.

使用的算法

我将使用KMP和Rabin Karp算法之间的混合来解决我的问题.Rabin Karp使用滚动哈希来比较初始字符串的子字符串.它需要使用线性附加内存的线性时间预计算,但从那时起,两个字符串的子串之间的比较是恒定的O(1)(如果正确处理冲突,这将分摊).

我的解决方案不会做什么

我的解决方案将找不到第一个字符串中与第二个字符串匹配的所有匹配项,最多只有1个差异.但是,可以修改算法,以便对于第一个字符串中的每个起始索引,如果存在这样的匹配,则将找到它们中的至少一个(这留给读者).

意见

我们m是第二个字符串的长度和n-第一个字符串的长度.我将把任务分成两部分:如果我的目标是找到最多只有一个差异的匹配,我想找到第一个字符串的子字符串:PREF将在单个差异之前SUFF的子字符串和之后的子字符串区别.我想要len(PREF) + len(SUFF) + 1 = m,如果需要,在人工缩短的地方PREF或SUFF将被缩短(当弦乐匹配时没有差别).

我将基于一个非常重要的观察来建立我的解决方案:假设第一个字符串的子字符串从索引开始,i其长度m与第二个字符串匹配,最多只有一个差异.然后,如果我们PREF尽可能长时间仍然会有解决方案SUFF.这是显而易见的:我只是尽可能地推动差异.

算法

现在遵循算法本身.从通常的KMP开始.每次前缀的扩展失败并且要遵循失败链接时,首先检查是否跳过下一个字母,剩余的后缀是否与第二个字符串的剩余部分匹配.如果是这样,则找到与最多一个字符差异的所寻求的匹配.如果没有 - 我们继续使用普通的KMP,每次跟踪失败链接时都要检查Rabin Karp.

让我用一个例子进一步澄清Rabin Karp检查.假设我们处于KMP的某个步骤,我们发现它first.substring[i, i + k - 1]匹配k第二个字符串的第一个字母.假设这封信first[i + k]不同于second[k].然后你检查是否first.substring[i + k + 1, i + m - 1]完全匹配second.substring[k + 1, m - 1]使用Rabin Karp.这正是您i尽可能多地扩展起始前缀表单索引的情况,现在尝试是否匹配最多只有一个差异.

只有在遵循失败链接时才会使用Rabin Karp,这会使前缀的起始索引至少移动一个,这意味着最多使用O(n)Rabin Karp调用,每个调用都具有复杂性O(1),总线性复杂度.