Sunday算法学习笔记

简介

Sunday算法是 Daniel M.Sunday 于1990年提出的一种字符串匹配算法。

KMP算法是一个里程碑似的算法，在这之后出现了许多字符串匹配的算法，Sunday算法就是其中之一。

KMP算法的时间和 string 库提供的函数速度相差无几，Sunday算法的效率则会比KMP快。

而且Sunday算法是一种极其容易理解的算法。

实现

Sunday算法的实现只比暴力匹配多了一个步骤，它在匹配失败时关注的是主串中参与匹配的最末尾字符的下一位字符，分为两种情况：

该字符没有在模式串中出现过，移动位数=模式串长度+1

该字符在模式串中出现过，移动位数=模式串中该字符最右出现的位置（以0开始）到尾部的距离+1 。

举个栗子，假定现在要在主串 substringsearchingxiaowu 中查找模式串 search

刚开始时，将两个字符串的左边对齐

结果是在第二个字符串处发现不匹配，此时关注文本串中参与匹配最末位字符的下一位字符，即绿色的字符 i ，因为模式串中并不存在 i ，所以将模式串直接跳过一大片，享有移动位数=6（模式串长度）+1=7，从 i 之后的那个字符 n 开始下一步匹配

结果第一个字符就不匹配，再看文本串中参与匹配最末位的下一位字符 r ，它出现在模式串倒数第三位，于是把模式串享有移动三位（ r 到模式串末尾的距离+1为3）使两个 r 对齐

匹配成功

基本代码实现（在母串str中寻找子串patten）：

#include