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 线性级别 内循环很长(若干次算术运算)能够处理流输入 正确性概率保证