题意整理。

  • 键盘输入两个字符串str和substr。
  • 求substr在str中出现的次数。

方法一（利用find函数）

1.解题思路

  • 首先将字符数组转化为字符串str1和str2。
  • 从str1下标i开始查找str2，如果找得到，计数加1，并且i从找到的位置，后移一位。

动图展示： alt

2.代码实现

#include <iostream>
#include <cstring>
using namespace std;

int main() {

    char str[100] = { 0 };
    char substr[100] = { 0 };

    cin.getline(str, sizeof(str));
    cin.getline(substr, sizeof(substr));

    int count = 0;

    //转化为字符串
    string str1(str);
    string str2(substr);
    
    int i=0;
    //从str1下标i开始查找str2
    while(str1.find(str2,i)!=-1){
        //如果找得到，计数加1
        count++;
        //i从找到的位置，后移一位
        i=str1.find(str2,i)+1;
    }

    cout << count << endl;

    return 0;
}

3.复杂度分析

  • 时间复杂度：find函数的时间复杂度为O(n+m)O(n+m)O(n+m)，最多查找n次，所以时间复杂度为O(n∗(n+m))O(n*(n+m))O(n∗(n+m))。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)O(1)。