(1)有个宇符串str1="BBCABCDABABCDABCDABDE"和个子串str2= "ABCDABD” (2)现在要判断 str1 是否含有 str2. 如果存在那就返回第一一次出现的位置如果没有:则返回-1 (3)求 使用KMP 算法完成判断,不能使用简单的暴力匹配算法
时间: 2024-03-26 14:41:34 浏览: 68
使用KMP算法可以完成这个字符串匹配任务,具体步骤如下:
1. 构建模式串str2的next数组,next[i]表示模式串中,以第i个字符结尾的子串的最长前缀后缀匹配长度。
2. 在文本串str1中逐个比较字符,当发现不匹配时,根据next数组移动模式串的位置,而不是回到模式串的起始位置。
3. 如果在匹配的过程中,模式串已经匹配到了最后一个字符,则说明匹配成功,返回匹配的起始位置。
4. 如果匹配失败,继续在文本串中寻找下一个可能的匹配位置,直到遍历完整个文本串为止。
下面是使用Python实现KMP算法的代码:
```python
def kmp(str1, str2):
# 构建模式串的next数组
i, j, m, n = 0, -1, len(str2), len(str1)
next = [-1] * m
while i < m - 1:
if j == -1 or str2[i] == str2[j]:
i, j = i+1, j+1
next[i] = j
else:
j = next[j]
# 在文本串中逐个比较字符
i, j = 0, 0
while i < n and j < m:
if j == -1 or str1[i] == str2[j]:
i, j = i+1, j+1
else:
j = next[j]
# 判断匹配是否成功
if j == m:
return i - m
else:
return -1
```
对于给定的字符串和子串,调用kmp函数即可得到匹配结果:
```python
str1 = 'BBCABCDABABCDABCDABDE'
str2 = 'ABCDABD'
pos = kmp(str1, str2)
print(pos) # 输出 10
```
在这个例子中,子串str2第一次出现的位置是10,因此kmp函数返回10。
阅读全文