题目
编写一个函数,计算一个子串在一个主串中出现的次数,如果该子串不出现,则返回0.本题不考虑子串重叠,如:主串为aaaa,子串为aa,考虑子串重叠结果为2,不考虑子串重叠结果为1。
分析
模式匹配算法的扩展,统计子串的出现次数。
代码
核心代码:
/* 计算子串在主串中出现的次数 */
/* str指的是主串;substr指的是子串 */
int index(Str str,Str substr){
int i=0,j=0,sum=0;
while(i<str.length&&j<substr.length){
if(str.ch[i]==substr.ch[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
if(j==substr.length){
j=0;
sum++;
}
}
return sum;
}
完整代码:
#include<stdio.h>
#include<stdlib.h>
#define maxSize 20
typedef struct {
char *ch;
int length;
} Str;
/* 打印字符串 */
void printStr(Str str) {
printf("\n");
for(int i=0; i<str.length; i++) {
printf("%c",str.ch[i]);
}
printf("\n");
}
/* 赋值操作 */
/* &str指的是新字符串;*ch指的是原字符串 */
int strAssign(Str &str,char *ch) {
if(str.ch) {// 如果原字符串有内容
free(str.ch);// 则释放原串空间
}
int len=0;
char *c=ch;// 求ch串的长度
while(*c) {
len++;
c++;
}
if(len==0) { // 如果ch为空串,则直接返回空串
str.ch=NULL;
str.length=0;
return 1;
} else {
str.ch=(char *)malloc(sizeof(char)*(len+1));// 取len+1是为了多分配一个空间存放"\0"字符
if(str.ch==NULL) {
return 0;
} else {
c=ch;
for(int i=0; i<=len; i++,c++) { // 注意:循环条件中之所以使用"<="是为了将ch最后的"\0"复制到新串中作为结束标记
str.ch[i]=*c;
}
str.length=len;
return 1;
}
}
}
/* 求字符串长度 */
int strLength(Str str) {
return str.length;// 返回字符串的长度
}
/* 计算子串在主串中出现的次数 */
/* str指的是主串;substr指的是子串 */
int index(Str str,Str substr){
int i=0,j=0,sum=0;
while(i<str.length&&j<substr.length){
if(str.ch[i]==substr.ch[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
if(j==substr.length){
j=0;
sum++;
}
}
return sum;
}
int main() {
Str str_t1,str_t2;
strAssign(str_t1,"ABABABCBABD");// 进行赋值操作
strAssign(str_t2,"AB");
printStr(str_t1);
printStr(str_t2);
printf("子串出现次数:%d",index(str_t1,str_t2));
return 0;
}
运行结果: