概率算法求解模式匹配问题

摘要

在长度为N的主串S中查找是否存在长度为M的模式串T,叫模式匹配问题。对于N和M均非常大的情况,概率算法求解此问题的效率比朴素算法和KMP算法要高。通过比较两个长度均为M的串的关联数是否相同,来确定这两个串是否相同。如果某它们的关联数不同,则这两个串一定不同;如果它们的关联数相同,则它们不同的概率很小,可忽略认为它们相同,也可将它们按位比较以便准确判断它们是否相同。本文计算长度为M的串的关联数的算法复杂度为O(1)。