Java教程

串匹配

本文主要是介绍串匹配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

链接:https://ac.nowcoder.com/acm/contest/23479/A

来源:牛客网

小红很喜欢红色(用'R'字母表示),但她非常讨厌紫色(用'P'字母表示)。
她想取一个连续子串,该子串包含至少 k 个'R'字符,且不能包含'P'字符。
你能告诉她有多少合法的方案可以取到吗?
注:只要连续子串的起始位置或终止位置不同,我们就认为是两个不同的方案。

识别到p就切割 问题转换成 统计满足k个p的字串有多少个
记录一个temp的数组
因为是子串 所以右端到左端满足k个的时候,就将
左端点向右走几次 就说明这个子串(右端点固定,左端点长度,长度减少的字串的数量)有几个
如 **rrr 区间不断减少
rrr
r
rr
满足条件的字串有两个 为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;
}
这篇关于串匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!