题目
题源：第十四届蓝桥杯（4960. 子串简写 - AcWing题库）
程序猿圈子里正在流行一种很新的简写方法：
对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。
例如 internationalization 简写成 i18n，Kubernetes 简写成 K8s，Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K
的字符串都可以采用这种简写方法（长度小于 K
的字符串不配使用这种简写）。
给定一个字符串 S和两个字符 c1和 c2
，请你计算 S
有多少个以 c1
开头 c2
结尾的子串可以采用这种简写？
输入格式
第一行包含一个整数 K
。
第二行包含一个字符串 S
和两个字符 c1
和 c2
。
输出格式
一个整数代表答案。
数据范围
对于 20%
的数据，2≤K≤|S|≤10000
。
对于 100%
的数据，2≤K≤|S|≤5×105
。S
只包含小写字母。c1
和 c2
都是小写字母。
|S|
代表字符串 S
的长度。
输入样例：
4
abababdb a b
输出样例：
6
样例解释
符合条件的子串如下所示，中括号内是该子串
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
暴力解法
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
LL sum[N];
string s;
int k;
char c1, c2;
int main()
{
cin >> k;
cin >> s;
cin >> c1 >> c2;
int n = s.size();
int ret = 0;
for(int i = 0;i < n;i++)
{
if(s[i] != c1) continue;
for(int j = i + 1;j < n;j++)
{
if(s[j] == c2)
{
int t = j - i + 1;
if(t >= k) ret++;
}
}
}
cout << ret << endl;
return 0;
}
标准解法（前缀和+双指针）
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
LL cnt[N]; //统计k个字符后每个位置后有多少个c2
string s;
int k;
char c1, c2;
int main()
{
cin >> k >> s >> c1 >> c2;
int n = s.size();
LL ret = 0;
for(int i = n - 1;i >= k - 1;i--)
{
if(s[i] == c2) cnt[i] = cnt[i + 1] + 1;
else cnt[i] = cnt[i + 1];
}
for(int i = 0;i <= n - k;i++)
{
if(s[i] != c1) continue;
int t = i + k - 1;
while(t < n && s[t] != c2) t++;
ret += cnt[t];
}
cout << ret << endl;
return 0;
}
//好题
题解
此题暴力解法非常好像，固定一边两层for循环就结束了。
但是标准解法里面前缀和的思想就不是那么好想了，从后往前的写法比较好写，往后计算应该也可以，但是我自己并没有尝试过。
整个题目思路是先处理k个字符后每个当前位置往后找有多少个c2字符，这样预处理，我们在计算每个c1能有多少个满足条件的子串的时候就可以快速得出，从本题可以得出的结论：在遍历的时候，需要快速计算某样东西时，可以思考前缀和，而不是只有求和的时候才能用。