给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)。
时间: 2024-02-13 10:05:55 浏览: 36
好的,这是一个经典的字符串匹配问题。常见的算法有暴力匹配、KMP算法、Boyer-Moore算法等。我来给您讲一下暴力匹配的算法思路。
暴力匹配算法,顾名思义,就是暴力地遍历s字符串,找到与n字符串第一个字符相同的位置,然后逐一比较s字符串和n字符串的每个字符是否相等。如果一直匹配到n字符串的最后一个字符都相等,则说明n字符串在s字符串中出现了,返回该位置;否则继续遍历s字符串,找到下一个与n字符串第一个字符相同的位置,重复上述步骤,直到遍历完整个s字符串。
下面是暴力匹配算法的代码实现:
```python
def str_str(s, n):
if not n:
return 0
if not s:
return -1
m, k = len(s), len(n)
for i in range(m-k+1):
if s[i:i+k] == n:
return i
return -1
```
接下来,我来给您提供一组测试用例,证明算法的正确性:
```python
assert str_str("hello", "ll") == 2
assert str_str("aaaaa", "bba") == -1
assert str_str("mississippi", "issip") == 4
```
这些测试用例可以验证暴力匹配算法的正确性。不过,暴力匹配算法的时间复杂度为O(mn),当s和n字符串较长时,效率会很低。KMP算法和Boyer-Moore算法可以在O(m+n)的时间复杂度内解决该问题,如果您感兴趣,我可以为您讲解。