Python|字符串匹配-Sunday算法
欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
问题描述
给两串字符串，找出子串在模式串中的位置。
例如：
输入：
S：‘abcabdabe’
T：‘abd’
输出：
3
解决方案
字符串匹配的问题有很多算法，这里用的是Sunday算法，Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
下面具体说一下Sunday算法的思路。
例如：
图 1 第一次匹配
先从头开始匹配，如果匹配不成功，则跳len(T)个。以上面为例，从下标为3的‘e’开始第二次。看‘e’是否在子串T中，发现不在，就说明模式串下标为0到3的范围内无法与子串T匹配，于是再把子串T向右移。
图 2 第二次匹配
再进行匹配，发现‘d’与‘y’不匹配，于是又跳一段，跳到模式串S中下标为7的‘q’。看‘q’是否在子串T中，发现在，移到对应位置看是否完全匹配。
图 3 匹配成功
发现全部匹配成功，此时，输出子串下标为0对应的下标即可。
代码示例：
|
def sunday(S, T): ls, lt = len(S), len(T) d = 0 #记录下标 while d <= ls - lt and T in S: #保证T有成为S子串的前提下并且循环 if S[d:d+lt] == T: #如果符合，返回下标 return d else: p = T.rfind(S[d+lt]) #返回字符串最后一次出现的位置，如果没有匹配项则返回-1 if p == -1: #没有匹配，跳子串长度个距离 d += lt + 1 else: #有匹配，对齐查看是否全部匹配 d += lt - p return False |
END
实习主编 | 王文星
责 编 | 周茂林
where2go 团队
微信号：算法与编程之美
长按识别二维码关注我们!
温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！