蓝桥杯/字串简写/c++
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如international-alization 简写成 i18n, Kubernetes(注意连字符不是字符串的一部分)简写成K8s ,Lanqiao 简写成L5o 等。在本题中,我们规定长度大于等于K的字符串都可以采用这种简写方法(长度小于K的字符串不配使用这种简写)。给定一个
·
问题描述
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如international-alization 简写成 i18n, Kubernetes(注意连字符不是字符串的一部分)简写成K8s ,Lanqiao 简写成L5o 等
在本题中,我们规定长度大于等于K的字符串都可以采用这种简写方法(长度小于K的字符串不配使用这种简写)。 给定一个字符串S和两个字符c1和c2,请你计算S有多少个以c1开头 c2结尾的字串可以采用这种简写?
输入格式
第一行包含一个整数K 。第二行包含一个字符串S和两个字符c1 和 c2.
输出格式
4
abababdb a b
样例输出
6
参考解法:
#include <bits/stdc++.h>
using namespace std;
int K;
long long ans=0,c1_sum=0;
string S;
char c1,c2;
int main(){
cin>>K>>S>>c1>>c2;
//以C2为右端点,找到距离大于等于K的所有C1,把每一个C2满足条件的C1数量都加起来即结果
for(int i=K-1,j=0;i<S.length();i++,j++)
{
if(S[j]==c1) c1_sum++;
if(S[i]==c2) ans+=c1_sum;
}
cout<<ans;
return 0;
}
//放缩思想,长的一定包含了短的情况,因此只要K的长度固定找到满足条件的即可
//每次都记录前指针有几次指向了a,由于指针的长度是一定满足K的,所以当后指针指向b的时候,我们就可以记录次数
法二:记录前缀和
#include<bits/stdc++.h>
using namespace std;
int n,l,c[500005];
long long sum;
char s[500005],a,b;
int main(){
scanf ("%d\n%s %c %c",&n,s+1,&a,&b);
l=strlen(s+1);
for(int i=1;i<=l;i++){
if (s[i]==a) c[i]++;
c[i]+=c[i-1];
if (i>=n&&s[i]==b){
sum+=c[i-n+1];
}
}
cout<<sum;
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)