模式匹配:KMP 算法

KMP 算法是在给定字符串中检索目标字符串的算法,该算法由Knuth、Morris 和 Pratt 三人在 Brute-Force 算法的基础上提出的模式匹配改进算法。该算法消除了 Brute-Force 在进行匹配时,只要遇到不相等字符就需要回退到本次比较起始位置的后一个位置继续开始新一轮的比较的缺点,这样的回退就把过程中所有的比较操作的时间付出全部给否定了,KMP 算法则正是需要在匹配失败时,利用之前的匹配结果,再不回退的情况下开始新的一轮比较,KMP 总会将目标字符串向前移动到合适的位置,保证当前指针前的字符串都是匹配的。

阅读全文

Powered by hexo & Theme by hiero   Copyright © 2015-2019 浙ICP备 16010916  号,指 · 间 All Rights Reserved.