字符串匹配算法之KMP&Boyer-Moore

时间:2021-10-27 15:58:44

KMP&Boyer-Moore

  KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候所需移动的下一个位置,直到达到字符串的末尾。KMP&Boyer-Moore算法是通过"字符串"与"搜索词"头部对齐,从尾部开始比较的一种方法。

KMP

  对于两个字符串:

1.用短的字符串的第一个字符开始依次与另外一个字符串进行比较

2.如果相同,继续比较下一位置的字符,否则,向后移动一定的距离(已经匹配上的字符个数-已经匹配字符串前缀和后缀对称的位数)

3.直到字符串的最后一位

Boyer-Moore

  各种文本编辑器的"查找"功能(Ctrl+F),就是采用的这种算法。

  算法思想却是很简单啊!与KMP不同,它是按照字符串的反向进行比较。

1.用短的字符串的第一个字符与另外一个字符串的起始位置对齐,比较最后一个字符

2.如果相同,继续比较前一个位置的字符,否则,移动一定的距离(不匹配字符个数-不匹配字符在短字符串中的上一次出现的位置)

参考:

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html