C语言经典例96-计算字符串中子串出现的次数

「爱情、让人受尽委屈。」 2023-07-07 12:31 19阅读 0赞

### 目录 ###

*  1 题目
 *  2 分析
 *  3 实现
 *  4 运行结果

# 1 题目 #

计算字符串中子串出现的次数

# 2 分析 #

串的模式匹配在数据结构中有KMP算法，但这个算法实现起来繁琐，难度很大，所以对于一般来说，使用暴力法求解，设有字符串`str`和子串`sub`，第一轮循环从`str`的第一个字符开始，设置一个位置标号`j`，再与子串`sub`逐个比较，若比较相同的话，则位置标号向后移，比较下一个字符，出现第一个不相同字符则该轮比较结束，比较结束后若`j`的值和`sub`字符串长度相同，则说明找到一个子串，计数`count`递增，第二轮循环则从`str`的第二个字符开始比较， 依次类推。

另外在`string.h`有函数`strstr()`，该函数返回在 haystack 中第一次出现 needle 字符串的位置，如果未找到则返回 null。函数原型如下：

char *strstr(const char *haystack, const char *needle)

*  haystack – 要被检索的 C 字符串。
 *  needle – 在 haystack 字符串内要搜索的小字符串。

# 3 实现 #

#include <stdio.h>
    #include <string.h>
    
    int subString(char *str,char *sub)
    { 
        int count = 0, i, j;
        for (i = 0; i < strlen(str); i++) { 
            for (j = 0; j < strlen(sub); j++) { 
                if(str[i + j] != sub[j]) { 
                    break; // 出现了不同字符就退出循环
                }
            }
            if (j == strlen(sub)) { 
                count++; // 退出循环后若j的值等于子串的长度，则存在子串
            }
        }
        return count;
    }
    
    int main(void)
    { 
        char str[100],sub[50];
        printf("请输入母串：");
        gets(str);
        printf("请输入子串：");
        gets(sub);
        printf("%d", subString(str,sub));
        return 0;
    }

# 4 运行结果 #

请输入母串：abcaabcaadbbc
    请输入子串：bc
    3