+- Rigorous and Reliable (RAR) (http://rar.shufangkeji.com:60380)
+-- Forum: 技术 (/forumdisplay.php?fid=242)
+--- Forum: 理论 (/forumdisplay.php?fid=246)
+--- Thread: 字符串匹配算法--Sunday算法 (/showthread.php?tid=2516)
字符串匹配算法--Sunday算法 - xwcwt - 12-03-2015 06:54 PM
“字符串模式匹配中超越BF、KMP和BM的算法
sunday算法的概念如下：
Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。“ -------引用自百度百科
当文本串为 Sunday searching algorithm
模式串为 search 时，第一次比较时，情形如下:
Sunday searching algorithm
search
此时 ‘S’ 和 ‘s' 不符合， 此时文本串就要移动， Sunday算法的思想是看此时参与比较的文本串中第一个字符的位置加上模式串长度之后的那个字符， 上述例子中参与比较的第一个文本串字符为S， 模式串长度为6， 此时要找的那个字符就是y后面的那个空格， 无论文本串怎样移动，这个空格字符串一定会参与下次的比较，如果该字符在模式串中出现，那么只要将文本串移动与模式串对应的字符位置相对应即可，如果该字符没有在模式串中出现，那么文本串就可以直接移动到该字符的下一个位置开始比较。在上述例子中由于空格没有在模式串中出现，所以文本串从空格以后的下一个字符's'开始比较，此时情况如下:
Sunday searching algorithm
search
此时比较发现模式串在文本串中出现。
当文本串为: goodday
模式串为 dog
第一次匹配时
goodday
dog
此时‘g'与'd'不匹配， 此时'o'后面的字符为'd’， d在模式串中出现， 第二次匹配时:
goodday
dog
发现‘d'和'o'不匹配， 'y’又没有在模式串中出现， 已经到文本串末尾，文本串不包含模式串。
2014/03/19 create by cwt