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