串匹配
2022/2/10 6:14:57
本文主要是介绍串匹配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:https://ac.nowcoder.com/acm/contest/23479/A
来源:牛客网
小红很喜欢红色(用'R'字母表示),但她非常讨厌紫色(用'P'字母表示)。
她想取一个连续子串,该子串包含至少 k 个'R'字符,且不能包含'P'字符。
你能告诉她有多少合法的方案可以取到吗?
注:只要连续子串的起始位置或终止位置不同,我们就认为是两个不同的方案。
识别到p就切割 问题转换成 统计满足k个p的字串有多少个
记录一个temp的数组
因为是子串 所以右端到左端满足k个的时候,就将
左端点向右走几次 就说明这个子串(右端点固定,左端点长度,长度减少的字串的数量)有几个
如 **rrr 区间不断减少
rrr
rrr
满足条件的字串有两个 为j走过的(减少的)数量
res+=j;
#include<bits/stdc++.h> using namespace std; int n,k; string s; long long res=0; void gao(string t){ //求字符串t中有多少子串包含至少k个'R' int i,j=0,temp=0; for(i=0;i<t.length();i++){//枚举右端点,找第一个不合法的左端点 temp+=t[i]=='R'; while(j<=i&&temp==k){ temp-=t[j++]=='R'; } //在这个左端点前面的都是合法的。 res+=j; } } int main(){ int i; cin>>n>>k>>s; string t=""; for(i=0;i<n;i++){ if(s[i]=='P')gao(t),t=""; else t+=s[i]; } gao(t); cout<<res; }
这篇关于串匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南