子字符串查找----各种算法总结

优点：

暴力查找算法：实现简单且在一般情况下工作良好（Java的String类型的indexOf()方法就是采用暴力子字符串查找算法）；

Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退；

Boyer-Moore算法的性能一般情况下都是亚线性级别；

Rabin-Karp算法是线性级别；

缺点：

暴力查找算法所需时间可能和NM成正比；

Knuth-Morris-Pratt算法和Boyer-Moore算法需要额外的内存空间；

Rabin-Karp算法内循环很长（若干次算术运算，其他算法都只需要比较字符）；

各种字符串查找算法实现的成本总结

* 概率保证，需要使用均匀和独立的散列函数。