采用顺序结构存储串,编写一个算法计算指定子串在一个字符串中出现的次数,如果该子串不出现则为0. (算法提示:使用BF模式匹配算法)
时间: 2024-03-10 21:46:03 浏览: 96
好的,我来为您编写这个算法。算法步骤如下:
1. 输入主串和子串;
2. 遍历主串,从第一个字符开始,依次与子串匹配;
3. 若主串当前字符与子串首字符不匹配,则主串指针后移一位;
4. 若主串当前字符与子串首字符匹配,则从当前位置开始依次比较主串和子串的后续字符;
5. 若比较完全匹配,则计数器加1,并将主串指针后移子串长度个位置;
6. 若比较未匹配,则主串指针后移一位,重复步骤3~5,直到主串遍历完毕。
7. 返回计数器的值,即为子串在主串中出现的次数。
算法实现如下(使用C语言):
```c
int BFCount(char* s, char* t) {
int i = 0, j = 0, count = 0;
while (s[i] != '\0') {
if (s[i] == t[j]) {
i++;
j++;
if (t[j] == '\0') {
count++;
j = 0;
i -= strlen(t) - 1;
}
} else {
j = 0;
i -= j - 1;
}
}
return count;
}
```
其中,s为主串,t为子串。在实现中,用i和j分别表示主串和子串的当前位置,count用于计数。当匹配成功时,将计数器加1,并将主串指针后移子串长度个位置;当匹配失败时,则将主串指针后移一位,重新开始匹配。
阅读全文