字符串匹配课件.ppt

1、字符串匹配田博雨字符串匹配 Brute-Force算法（暴力算法）Knuth-Morris-Pratt算法 Boyer-Moore算法 Rabin-Karp算法暴力算法暴力算法的复杂度 在最差情况下：O(mn)在一般情况下：接近于O(n)实现一实现二Knuth-Morris-Pratt算法 避免指针回退到已知的字符之前 P：模式字符串 Px：P的前x个字符构成的串(x)：除Px外，可以成为Px后缀的P的最长前缀的长度KMPKMP的实现如何计算(x)？对模式字符串P进行KMP的过程KMP的复杂度 O(n+m)预处理O(m)，匹配O(n)Boyer-Moore算法 指针i从左向右扫描文本，指针j从

2、右向左扫描模式字符串 记录重启位置的数组rightc记录字符c在模式字符串中出现的最靠右的位置。匹配失败的字符不在模式字符串中将模式字符串向右移动(j+1)个位置 匹配失败的字符在模式字符串中用right将模式字符串和文本对齐，使得该字符和它在模式字符串中出现的最右位置相匹配（将i增大j-rightc）如果这样无法增大i，则将i加1，保证模式字符串至少向右移动了1个位置BM的复杂度 最差情况：O(mn)一般情况：O(n/m)Rabin-Karp算法基于哈希的算法 验证？不验证？验证：O(mn)不验证：O(n)不验证的正确率？总结 暴力算法 一般情况下接近线性 查找时间可能达到MN的级别 Java中String类的indexOf()使用此方法总结 Knuth-Morris-Pratt算法 保证线性级别 不需要在正文中回退 能够处理流输入 需要额外的内存空间总结 Boyer-Moore算法 一般情况下是亚线性级别 可能与MN成正比 需要额外内存空间总结 Rabin-Karp 线性级别 内循环很长（若干次算术运算）能够处理流输入 正确性概率保证