1、字符串匹配问题 给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1
时间: 2024-01-22 21:21:02 浏览: 27
这是一个经典的字符串匹配问题,常见的解法有暴力匹配、KMP算法、Boyer-Moore算法等。其中KMP算法和Boyer-Moore算法是比较高效的解法。
以下是KMP算法的实现:
```python
def kmp(s, n):
# 构建next数组
next = [0] * len(n)
j = 0
for i in range(1, len(n)):
while j > 0 and n[i] != n[j]:
j = next[j-1]
if n[i] == n[j]:
j += 1
next[i] = j
# 匹配字符串
j = 0
for i in range(len(s)):
while j > 0 and s[i] != n[j]:
j = next[j-1]
if s[i] == n[j]:
j += 1
if j == len(n):
return i - j + 1
return -1
```
其中next数组表示n字符串中每个位置之前的字符串的最长公共前后缀的长度。在匹配字符串时,如果当前字符不匹配,则通过next数组回溯到之前匹配的位置继续匹配。如果匹配成功,则返回起始位置。
示例:
```python
s = "hello world"
n = "world"
print(kmp(s, n)) # 输出 6
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)