解题思路

“子串”的意思是：b 在 a 里连续的一段和它完全一样，那么 b 就是 a 的子串。题目问的是 a 里一共能找出多少个 b。

注意！字符串 a 和 b 都可能包含空格，所以不能用 cin >> 读（它遇到空格就停了），要用 getline 一次读一整行。

数子串的办法：

1. 用 find 在 a 里找 b，找到的位置记下来，答案加 1；
2. 从找到位置的下一个位置继续找，这样像 aaaa 里找 aa 这种重叠的情况也能数到：
   • 第 1 个 aa 在第 0~1 位；
   • 再从第 1 位开始找，第 2 个 aa 在第 1~2 位；
   • 再从第 2 位开始找，第 3 个 aa 在第 2~3 位；
   • 一共 3 个。
3. find 找不到的时候会返回一个特殊值 string::npos，表示“不存在”，这时就结束循环。

用样例验证：a=welcome to my hometown!，b=me。在 welcome 里找到第 1 个 me，在 hometown 里找到第 2 个 me，一共 2 个，和样例一致。

参考代码

// P4551 子串个数：统计b在a中出现的次数（允许重叠）
#include <iostream>
#include <string>
using namespace std;
int main() {
    string a, b;
    getline(cin, a);          // 第1行可能含空格，用getline读整行
    getline(cin, b);          // 第2行可能含空格，同样用getline
    int cnt = 0;
    int pos = 0;
    // 反复从a中查找b，找到一次答案加1，再从下一个位置继续找
    while (true) {
        pos = a.find(b, pos);
        if (pos == string::npos) break;  // 找不到了就结束
        cnt++;
        pos++;                 // 从下一位置继续，允许重叠统计
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

• a 的长度不超过 1000，b 不超过 20。每次 find 最多比较 O(a 的长度 × b 的长度) 次，最多找 O(a 的长度) 次。
• 总时间复杂度 O(n × m)，n≤1000、m≤20，非常快；
• 空间复杂度 O(1)，只用了两个字符串变量。