Sunday算法(字符串匹配)

Sunday算法由Daniel M.Sunday在1990年提出。是一种效率很快的字符串匹配算法
首先我们称字符串T为文本串,字符串P为模式串,要求的是P是否在T中出现过,或T在P中出现的位置。
匹配规则:
从前往后匹配,如果匹配失败,即模式串中的当前字符与文本串中的当前字符不一样,就后移。后移的规则跟文本串中参与匹配的下一位字符有关。
1.如果该字符没有在模式串中出现则直接跳过,即移动位数 = 匹配串长度 + 1;
2.否则,其移动位数 = 模式串中最右端的该字符到末尾的距离+1。
举个例子说明一下。
文本串:Here is a simple example
模式串: example
Sunday算法(字符串匹配)
这里H和e不匹配,按照匹配规则我们看文本串中参与匹配的字符串下一个位置,即s后的空格字符。满足匹配条件1,这样我们就后移7+1=8位
Sunday算法(字符串匹配)
然后继续匹配,a和e还是匹配失败,继续看文本串中参与匹配的下一位字符,即e,由于e在模式串中出现过,我们执行后移规则2,即0+1=1位。

Sunday算法(字符串匹配)
e和空格不一样,匹配失败,此时关注simple后面的空格字符,由于模式串中没有空格字符,所以执行后移规则1,即7+1=8位
Sunday算法(字符串匹配)
整个过程只移动了3次,可以看出效率非常高。

上一篇:ES6基础知识——设置对象的prototype Object.setPrototypeOf()


下一篇:如何使用gitbook写文档