boyer-moore 算法python代码
时间: 2023-10-26 14:07:37 浏览: 28
我很高兴回答你的问题!下面是 Boyer-Moore 算法的 Python 代码实现:
```python
def boyer_moore(s, p):
m = len(p)
n = len(s)
if m > n:
return -1
skip = [m] * 256
for k in range(m - 1):
skip[ord(p[k])] = m - k - 1
skip = tuple(skip)
k = m - 1
while k < n:
j = m - 1
i = k
while j >= 0 and s[i] == p[j]:
i -= 1
j -= 1
if j == -1:
return i + 1
k += skip[ord(s[k])]
return -1
```
希望能对您有所帮助!
相关问题
boyer-moore算法的python代码
以下是 Boyer-Moore 算法的 Python 代码实现:
```python
def bad_character_table(pattern):
# 构建坏字符哈希表
table = {}
for i in range(len(pattern)):
table[pattern[i]] = i
return table
def good_suffix_table(pattern):
# 构建好后缀哈希表
table = [-1] * len(pattern)
for i in range(len(pattern)):
j = i - 1
while j >= 0 and pattern[j:j+len(pattern)-i] == pattern[i:]:
j -= 1
table[len(pattern)-i-1] = j+1
return table
def boyer_moore(text, pattern):
m, n = len(pattern), len(text)
if m > n:
return -1
bad_char_table = bad_character_table(pattern)
good_suffix_table = good_suffix_table(pattern)
i = 0
while i <= n-m:
j = m-1
while j >= 0 and pattern[j] == text[i+j]:
j -= 1
if j == -1:
return i
bad_char_index = bad_char_table.get(text[i+j], -1)
i += max(j - bad_char_index, good_suffix_table[m-j-1])
return -1
```
其中,`bad_character_table` 函数用于构建坏字符哈希表,`good_suffix_table` 函数用于构建好后缀哈希表,`boyer_moore` 函数用于实现 Boyer-Moore 算法的主体部分。在 `boyer_moore` 函数中,首先判断模式串长度是否大于文本串长度,若是则返回 -1。接着,分别构建坏字符哈希表和好后缀哈希表,并将游标 i 指向文本串的起始位置。在循环中,游标 j 从模式串结尾处向前匹配,若匹配成功则 j 减一,否则通过坏字符哈希表和好后缀哈希表计算出新的游标 i,并将游标 j 重置为模式串结尾。最终,若未能匹配则返回 -1。
Boyer-Moore算法用python实现
好的,以下是Boyer-Moore算法的Python实现:
```python
def boyer_moore(text, pattern):
n = len(text)
m = len(pattern)
if m == 0:
return 0
last = {}
for i in range(m):
last[pattern[i]] = i
i = m - 1
k = m - 1
while i < n:
if text[i] == pattern[k]:
if k == 0:
return i
i -= 1
k -= 1
else:
j = last.get(text[i], -1)
i += m - min(k, j + 1)
k = m - 1
return -1
```
以上代码实现了Boyer-Moore算法的匹配过程。其中,`text`是待匹配的文本,`pattern`是要查找的模式。函数返回模式在文本中第一次出现的位置。如果没有找到,返回-1。