串匹配

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

链接：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;
}

这篇关于串匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！