自动搬运

查看原文

来自洛谷，原作者为

	dbywsc **

搬运于2025-08-24 22:46:43，当前版本为作者最后更新于2025-03-29 11:30:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

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

指针 $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;
}