AcWing 4960. 子串简写
原题链接
中等
作者:
너
,
2024-04-11 12:52:12
,
所有人可见
,
阅读 2
算法1
(暴力枚举) $O(n^2)$
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
char s[N];
char a, b;
int n, res; //长度
int main(){
cin >> n;
cin >> s >> a >> b;
int len = strlen(s);
for(int i = 0, j = 0; i < len; i ++ ) //枚举字串的开头
{
if(s[i] != a) continue;
for(int j = i + n - 1; j < len; j ++ ) //枚举字串的结尾
{
if(s[j] == b) res ++;
}
}
cout << res << endl;
return 0;
}
算法2
前缀和思想 $O(n)$
依次统计前缀序列中c1的数量,用cnt[i]表示长度为i的前缀序列中c1的个数。然后从下标k处开始枚举以c2结尾的长度>=k的子串,假设此时以c2结尾的坐标为i, 则cnt[i - k + 1]就是以c2结尾长度>=k的字串,且字串首个元素为c1的所有序列。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
char s[N];
int k;
LL res;
char c1, c2;
int cnt1[N], cnt2[N];
int main()
{
cin >> k;
cin >> s + 1 >> c1 >> c2;
int n = strlen(s + 1);
for(int i = 1; i <= n; i ++ )
{
cnt1[i] = cnt1[i - 1];
cnt2[i] = cnt2[i - 1];
if(s[i] == c1) cnt1[i] ++;
if(s[i] == c2) cnt2[i] ++;
}
//for(int i = 1; i <= n; i ++ ) cout << cnt1[i] << ' ' << cnt2[i] << endl;
for(int i = k; i <= n; i ++ )
{
if(s[i] == c2)
{
res += cnt1[i - k + 1];
}
}
cout << res << endl;
return 0;
}