实现Horspool字符串匹配 【输入形式】文本串和模式串(分开输入) 【输出形式】匹配成功,输出模式首字符对应文本的字符下标(从0开始);失败输出-1 同时输出字符比较次数 【样例输入】0001000000(文本) 100(模式) 【样例输出】3 7 (成功案例: 即匹配位置与比较次数,中间用空格隔开)
时间: 2024-03-05 14:53:26 浏览: 84
字符串匹配算法之Horspool算法
好的,我会实现Horspool字符串匹配算法来回答你的问题。
以下是实现代码:
```python
def horspool(text, pattern):
m = len(pattern)
n = len(text)
if m > n:
return -1, 0
skip = [m] * 256
for k in range(m - 1):
skip[ord(pattern[k])] = m - k - 1
skip = tuple(skip)
k = m - 1
comparisons = 0
while k < n:
j = m - 1
i = k
while j >= 0 and text[i] == pattern[j]:
comparisons += 1
j -= 1
i -= 1
if j == -1:
return i + 1, comparisons
k += skip[ord(text[k])]
return -1, comparisons
```
这个函数接受两个字符串参数 `text` 和 `pattern`,分别表示文本串和模式串。它返回一个元组,第一个元素表示匹配成功时模式串首字符在文本串中的下标,匹配失败时返回 -1;第二个元素表示字符比较次数。
使用这个函数来解决你的问题,代码如下:
```python
text = input()
pattern = input()
index, comparisons = horspool(text, pattern)
if index == -1:
print(index)
else:
print(index, comparisons)
```
你可以将文本串和模式串分别输入,然后调用 `horspool` 函数得到匹配结果和字符比较次数。
阅读全文