成都教育网站建设,在贸易网站怎么做贸易,企业咨询公司名称大全,工作证设计风格1. Sunday 算法介绍
「Sunday 算法」 是一种在字符串中查找子串的算法#xff0c;是 Daniel M.Sunday 于1990年提出的字符串模式匹配算法。 Sunday 算法思想#xff1a;对于给定文本串 T 与模式串 p#xff0c;先对模式串 p 进行预处理。然后在匹配的过程中#xff0c;当发…1. Sunday 算法介绍
「Sunday 算法」 是一种在字符串中查找子串的算法是 Daniel M.Sunday 于1990年提出的字符串模式匹配算法。 Sunday 算法思想对于给定文本串 T 与模式串 p先对模式串 p 进行预处理。然后在匹配的过程中当发现文本串 T 的某个字符与模式串 p 不匹配的时候根据启发策略能够尽可能的跳过一些无法匹配的情况将模式串多向后滑动几位。 Sunday 算法思想跟 Boyer Moore 算法思想类似。不同的是Sunday 算法匹配顺序是从左向右并且在模式串 p 匹配失败时关注的是文本串 T 中参加匹配的末尾字符的下一位字符。当文本串 T 中某个字符跟模式串 p 的某个字符不匹配时可以将模式串 p 快速向右移动。
遇到不匹配字符时可以根据以下两种情况向右快速进行移动
情况 1文本串 T 中与模式串 p 尾部字符 p[m - 1] 对应的字符下一个位置的字符 T[i m] 出现在模式串 p 中。 这种情况下可将T[i m] 与模式串中最后一次出现的该字符对齐如下图所示。向右移动位数 文本串 T 中与模式串 p 尾部位置的下一个位置 - T[i m] 在模式串中最后一次出现的位置。注意文本串 T 中与模式串 p 尾部位置的下一个位置其实就是「模式串长度」。 情况 2文本串 T 中与模式串 p 尾部字符 p[m - 1] 对应的字符下一个位置的字符 T[i m] 没有出现在模式串 p 中。 这种情况下可将模式串整个右移如下图所示。向右移动位数 整个模式串长度 1。 2. Sunday 算法步骤
整个 Horspool 算法步骤描述如下
计算出文本串 T 的长度为 n模式串 p 的长度为 m。先对模式串 p 进行预处理生成后移位数表 bc_table。将模式串 p 的头部与文本串 T 对齐将 i 指向文本串开始位置即 i 0。j 指向模式串开始即 j 0然后从模式串开始位置开始比较。 如果文本串对应位置的字符 T[i j] 与模式串对应字符 p[j] 相同则继续比较后一位字符。 如果模式串全部匹配完毕则返回模式串 p 在文本串中的开始位置 i。 如果文本串对应位置的字符 T[i j] 与模式串对应字符 p[j] 不同则 根据后移位数表 bc_table 和模式串末尾位置对应的文本串上的字符 T[i m] 计算出可移动距离 bc_table[T[i m]]然后将模式串进行后移。 如果移动到末尾也没有找到匹配情况则返回 -1。
3. Sunday 算法代码实现
3.1 后移位数表代码实现
生成后移位数表的代码实现比较简单跟 Horspool 算法中生成后移位数表的代码差不多。具体步骤如下
使用一个哈希表 bc_table bc_table[bad_char] 表示表示遇到坏字符可以向右移动的距离。遍历模式串以当前字符 p[i] 为键可以向右移动的距离m - i为值存入字典中。如果出现重复字符则新的位置下标值会将之前存放的值覆盖掉。这样哈希表中存放的就是该字符在模式串中出现最右侧位置上的可向右移动的距离。
如果在 Sunday 算法的匹配过程中如果 T[i m] 不在 bc_table 中时可令其为 m 1表示可以将模式串整个右移到上一次匹配末尾后边两个位置上。如果 T[i m] 在 bc_table 中时可移动距离就是 bc_table[T[i m]] 。这样就能计算出可以向右移动的位数了。
生成后移位数表的代码如下
# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离
def generateBadCharTable(p: str):m len(p)bc_table dict()for i in range(m): # 迭代到最后一个位置 m - 1bc_table[p[i]] m - i # 更新遇到坏字符可向右移动的距离return bc_table3.2 Sunday 算法整体代码实现
# sunday 算法T 为文本串p 为模式串
def sunday(T: str, p: str) - int:n, m len(T), len(p)bc_table generateBadCharTable(p) # 生成后移位数表i 0while i n - m:j 0if T[i: i m] p:return i # 匹配完成返回模式串 p 在文本串 T 的位置if i m n:return -1i bc_table.get(T[i m], m 1) # 通过后移位数表向右进行进行快速移动return -1 # 匹配失败# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离
def generateBadCharTable(p: str):m len(p)bc_table dict()for i in range(m): # 迭代到最后一个位置 m - 1bc_table[p[i]] m - i # 更新遇到坏字符可向右移动的距离return bc_tableprint(sunday(abbcfdddbddcaddebc, aaaaa))
print(sunday(abbcfdddbddcaddebc, bcf))4. Sunday 算法分析
Sunday 算法在平均情况下的时间复杂度为 O ( n ) O(n) O(n)但是在最坏情况下时间复杂度会退化为 O ( n ∗ m ) O(n * m) O(n∗m)。
