题解：P9244 [蓝桥杯 2023 省 B] 子串简写

· · 题解

思路

用两个指针遍历字符串即可。

指针 i 开始时指向第一位，指针 j 开始时指向第 k 位，如果 i 指针指向的字符是 c_{1} 就用 cnt 记录一下当前 c_{1} 出现过的次数，如果 j 指针指向 c_{2} 就让 ans 加上 cnt。这样的话在每次遇到 c_{2} 时之前记录的 c_{1} 都可以与它组成子串，能够覆盖所有长度不小于 k 的子串的情况。

代码

void solve(void) {
    int k; string s; char c1, c2;
    cin >> k >> s >> c1 >> c2;
    int ans = 0, cnt = 0;
    s = " " + s;
    for(int i = 1, j = k; j <= s.length(); i++, j++) {
        if(s[i] == c1) cnt++;
        if(s[j] == c2) ans += cnt;
    }
    cout << ans << endl;
}