首页 > 其他 > 详细

Knuth-Morris-Pratt Search vs Boyer-Moore Search

时间:2018-06-07 18:36:04      阅读:153      评论:0      收藏:0      [点我收藏+]

Reference

[1] https://stackoverflow.com/questions/12656160/what-are-the-main-differences-between-the-knuth-morris-pratt-and-boyer-moore-sea?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

[2] http://www.cs.utexas.edu/~moore/best-ideas/string-searching/kpm-example.html

[3] http://www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html

Boyer-Moore‘s approach is to try to match the last character of the pattern instead of the first one with the assumption that if there‘s not match at the end no need to try to match at the beginning. This allows for "big jumps" therefore BM works better when the pattern and the text you are searching resemble "natural text" (i.e. English)

Knuth-Morris-Pratt searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (Source: Wiki)

This means KMP is better suited for small sets like DNA (ACTG)

Boyer-Moore technique match the characters from right to left, works well on long patterns. knuth moris pratt match the characters from left to right, works fast on short patterns.

 

Knuth-Morris-Pratt Search vs Boyer-Moore Search

原文:https://www.cnblogs.com/codingforum/p/9151878.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!