代码拉取完成,页面将自动刷新
同步操作将从 程序员充电站/LeetCode-Py 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Horspool 算法:是一种在字符串中查找子串的算法,它是由 Nigel Horspool 教授于 1980 年出版的,是首个对 Boyer Moore 算法进行简化的算法。
- Horspool 算法思想:对于给定文本串
T
与模式串p
,先对模式串p
进行预处理。然后在匹配的过程中,当发现文本串T
的某个字符与模式串p
不匹配的时候,根据启发策略,能够尽可能的跳过一些无法匹配的情况,将模式串多向后滑动几位。
可以看出,Horspool 算法思想和 Boyer Moore 算法思想是一致的。Horspool 算法是在 Boyer Moore 算法思想基础上改进了「坏字符规则」。当文本串 T
中某个字符跟模式串 p
的某个字符不匹配时,可以模式串 p
快速向右移动。
遇到不匹配字符时,可以根据以下两种情况向右快速进行移动:
T
中与模式串 p
尾部字符 p[m - 1]
对应的字符 T[i + m - 1]
出现在模式串 p
中。
T[i + m - 1]
与模式串中最后一次出现的该字符对齐,如下图所示。T
中与模式串 p
尾部字符 p[m - 1]
对应的字符 T[i + m - 1]
没有出现在模式串 p
中。
整个 Horspool 算法步骤描述如下:
T
的长度为 n
,模式串 p
的长度为 m
。p
进行预处理,生成后移位数表 bc_table
。p
的头部与文本串 T
对齐,将 i
指向文本串开始位置,即 i = 0
。j
指向模式串末尾位置,即 j = m - 1
,然后从模式串末尾位置开始比较。
T[i + j]
与模式串对应字符 p[j]
相同,则继续比较前一位字符。
p
在文本串中的开始位置 i
。T[i + j]
与模式串对应字符 p[j]
不同,则:
bc_table
和模式串末尾位置对应的文本串上的字符 T[i + m - 1]
,计算出可移动距离 bc_table[T[i + m - 1]]
,然后将模式串进行后移。-1
。生成后移位数表的代码实现比较简单,跟 Boyer Moore 算法中生成坏字符位置表的代码差不多。具体步骤如下:
bc_table
, bc_table[bad_char]
表示表示遇到坏字符可以向右移动的距离。p[i]
为键,可以向右移动的距离(m - 1 - i
)为值存入字典中。如果出现重复字符,则新的位置下标值会将之前存放的值覆盖掉。这样哈希表中存放的就是该字符在模式串中出现最右侧位置上的可向右移动的距离。如果在 Horspool 算法的匹配过程中,如果 T[i + m - 1]
不在 bc_table
中时,可令其为 m
,表示可以将模式串整个右移。如果 T[i + m - 1]
在 bc_table
中时,可移动距离就是 bc_table[T[i + m - 1]]
。这样就能计算出可以向右移动的位数了。
生成后移位数表的代码如下:
# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离
def generateBadCharTable(p: str):
m = len(p)
bc_table = dict()
for i in range(m - 1): # 迭代到 m - 2
bc_table[p[i]] = m - 1 - i # 更新遇到坏字符可向右移动的距离
return bc_table
# horspool 算法,T 为文本串,p 为模式串
def horspool(T: str, p: str) -> int:
n, m = len(T), len(p)
bc_table = generateBadCharTable(p) # 生成后移位数表
i = 0
while i <= n - m:
j = m - 1
while j > -1 and T[i + j] == p[j]: # 进行后缀匹配,跳出循环说明出现坏字符
j -= 1
if j < 0:
return i # 匹配完成,返回模式串 p 在文本串 T 中的位置
i += bc_table.get(T[i + m - 1], m) # 通过后移位数表,向右进行进行快速移动
return -1 # 匹配失败
# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离
def generateBadCharTable(p: str):
m = len(p)
bc_table = dict()
for i in range(m - 1): # 迭代到 m - 2
bc_table[p[i]] = m - 1 - i # 更新遇到坏字符可向右移动的距离
return bc_table
print(horspool("abbcfdddbddcaddebc", "aaaaa"))
print(horspool("abbcfdddbddcaddebc", "bcf"))
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。