优点:
暴力查找算法:实现简单且在一般情况下工作良好(Java的String类型的indexOf()方法就是采用暴力子字符串查找算法);
Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退;
Boyer-Moore算法的性能一般情况下都是亚线性级别;
Rabin-Karp算法是线性级别;
缺点:
暴力查找算法所需时间可能和NM成正比;
Knuth-Morris-Pratt算法和Boyer-Moore算法需要额外的内存空间;
Rabin-Karp算法内循环很长(若干次算术运算,其他算法都只需要比较字符);
各种字符串查找算法实现的成本总结
算法 | 版本 | 最坏情况 | 一般情况 | 是否回退 | 正确性 | 额外空间需求 |
---|---|---|---|---|---|---|
暴力算法 | -- | MN | 1.1N | 是 | 是 | 1 |
KMP算法 | 完整的DFA(博客中实现的方法) | 2N | 1.1N | 否 | 是 | MR |
仅构造不匹配的状态转换 | 3N | 1.1N | 否 | 是 | M | |
完整版本 | 3N | N/M | 是 | 是 | R | |
Boyer-Moore算法 | 启发式查找不匹配字符 | MN | N/M | 是 | 是 | R |
Rabin-Karp算法 | 蒙特卡洛算法 | 7N | 7N | 否 | 是* | 1 |
拉斯维加斯算法 | 7N* | 7N | 是 | 是 | 1 |
* 概率保证,需要使用均匀和独立的散列函数。