用python编写字符串匹配问题 给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)
时间: 2024-02-13 13:07:18 浏览: 69
好的,这是一个常见的字符串匹配问题,可以使用 KMP 算法来解决。以下是 Python 代码实现:
```python
def kmp(s: str, n: str) -> int:
if not n:
return 0
if not s:
return -1
next = get_next(n)
i, j = 0, 0
while i < len(s) and j < len(n):
if j == -1 or s[i] == n[j]:
i += 1
j += 1
else:
j = next[j]
if j == len(n):
return i - j
else:
return -1
def get_next(n: str) -> List[int]:
next = [-1] * len(n)
i, j = 0, -1
while i < len(n) - 1:
if j == -1 or n[i] == n[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
```
接下来是一些测试用例,验证该算法的正确性:
```python
assert kmp('hello, world!', 'world') == 7
assert kmp('hello, world!', 'hello') == 0
assert kmp('hello, world!', 'o, w') == 4
assert kmp('hello, world!', 'hi') == -1
assert kmp('', 'hi') == -1
assert kmp('hello, world!', '') == 0
assert kmp('', '') == 0
```
以上代码实现了 KMP 算法,并且提供了多个测试用例,证明了算法的正确性。
阅读全文