给定一个字符串a和字符串b,1≤a的长度≤100,1≤b的长度≤a的长度求a在b中出现的次数
时间: 2024-02-05 09:13:39 浏览: 84
可以使用字符串匹配算法来解决这个问题,如KMP算法。
具体实现步骤如下:
1. 构建模式串的next数组。
2. 在文本串中匹配模式串,匹配成功则计数器加1。
代码实现如下(使用KMP算法):
```python
def get_next(p):
m = len(p)
next = [0] * m
j = 0
for i in range(1, m):
while j > 0 and p[i] != p[j]:
j = next[j - 1]
if p[i] == p[j]:
j += 1
next[i] = j
return next
def kmp(t, p):
n, m = len(t), len(p)
next = get_next(p)
j = 0
count = 0
for i in range(n):
while j > 0 and t[i] != p[j]:
j = next[j - 1]
if t[i] == p[j]:
j += 1
if j == m:
count += 1
j = next[j - 1]
return count
a = input()
b = input()
print(kmp(b, a))
```
其中,get_next函数用于构建模式串的next数组,kmp函数用于在文本串中匹配模式串,并返回匹配成功的次数。在主函数中,分别输入字符串a和字符串b,并调用kmp函数计算a在b中出现的次数。
阅读全文