给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)。
时间: 2024-02-22 20:56:08 浏览: 59
可以使用字符串匹配算法来解决这个问题,常用的算法有暴力匹配算法、KMP算法、Boyer-Moore算法等。
下面给出使用暴力匹配算法的示例代码:
```python
def str_str(s: str, n: str) -> int:
s_len, n_len = len(s), len(n)
if n_len == 0:
return 0
for i in range(s_len - n_len + 1):
j = 0
while j < n_len and s[i+j] == n[j]:
j += 1
if j == n_len:
return i
return -1
```
这个算法的时间复杂度为 $O(mn)$,其中 $m$ 和 $n$ 分别是字符串 $s$ 和字符串 $n$ 的长度。在最坏情况下,需要对每个子串都进行一次完整的比较,因此时间复杂度较高。
下面给出几个测试用例:
```python
assert str_str("hello", "ll") == 2
assert str_str("aaaaa", "bba") == -1
assert str_str("mississippi", "issip") == 4
```
以上测试用例分别对应了 $s$ 中存在 $n$ 子串的情况、$s$ 中不存在 $n$ 子串的情况以及 $s$ 中存在多个重叠的 $n$ 子串的情况,都可以正确地返回 $n$ 子串在 $s$ 中的位置。
阅读全文