用KMP算法求子串在主串中出现的次数
时间: 2024-02-12 13:32:02 浏览: 28
好的,以下是使用KMP算法求子串在主串中出现的次数的代码实现:
```python
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
lps = [0]*M
j = 0
computeLPSArray(pat, M, lps)
i = 0
res = 0
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
res += 1
j = lps[j-1]
elif i < N and pat[j] != txt[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
return res
def computeLPSArray(pat, M, lps):
len = 0
lps[0] = 0
i = 1
while i < M:
if pat[i] == pat[len]:
len += 1
lps[i] = len
i += 1
else:
if len != 0:
len = lps[len-1]
else:
lps[i] = 0
i += 1
```
其中,`pat`是要查找的子串,`txt`是主串。函数`KMPSearch`返回子串在主串中出现的次数。