def GetNext(t,next): #由模式串t求出next值 next[0] = -1 i,j=0,-1 while i < len(t) - 1: if j == -1 or t[i] == t[j]: i,j=i+1, j+1 next[i] = j else: j=next def StrCount2(s, t): # KMP算法求解 i, j, cnt = 0, 0, 0 next = [-1] * len(t) GetNext(t, next) while i < len(s): if j == -1 or s[i] == t[j]: i, j = i + 1, j + 1 else: j = next[j] if j == len(t): cnt += 1 j = 0 return cnt
时间: 2024-01-05 19:03:19 浏览: 108
这段代码存在一些问题,我将逐一列举并给出修改建议:
1. GetNext 函数中的第 7 行和第 9 行缺少缩进,导致语法错误。正确的代码应该是:
```python
def GetNext(t, next):
next[0] = -1
i, j = 0, -1
while i < len(t) - 1:
if j == -1 or t[i] == t[j]:
i, j = i + 1, j + 1
next[i] = j
else:
j = next[j]
```
2. GetNext 函数中的第 8 行和第 10 行缺少 j 的更新,导致 next 数组计算错误。正确的代码应该是:
```python
def GetNext(t, next):
next[0] = -1
i, j = 0, -1
while i < len(t) - 1:
if j == -1 or t[i] == t[j]:
i, j = i + 1, j + 1
next[i] = j if t[i] != t[j] else next[j]
else:
j = next[j]
```
3. StrCount2 函数中的第 10 行缺少缩进,导致语法错误。正确的代码应该是:
```python
def StrCount2(s, t):
# KMP算法求解
i, j, cnt = 0, 0, 0
next = [-1] * len(t)
GetNext(t, next)
while i < len(s):
if j == -1 or s[i] == t[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == len(t):
cnt += 1
j = 0
return cnt
```
综上所述,修改后的代码如下:
```python
def GetNext(t, next):
next[0] = -1
i, j = 0, -1
while i < len(t) - 1:
if j == -1 or t[i] == t[j]:
i, j = i + 1, j + 1
next[i] = j if t[i] != t[j] else next[j]
else:
j = next[j]
def StrCount2(s, t):
# KMP算法求解
i, j, cnt = 0, 0, 0
next = [-1] * len(t)
GetNext(t, next)
while i < len(s):
if j == -1 or s[i] == t[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == len(t):
cnt += 1
j = 0
return cnt
```
阅读全文