字串简写——前缀和+回溯

#include<bits/stdc++.h>

#include<cstdio> 

#include<cstring>

using namespace std;

typedef long long LL;

LL K;

char S[600000];

char c1,c2;

int main(){

    ios::sync_with_stdio(0);cin.tie(0);

    cin>>K>>S>>c1>>c2;

    LL n=strlen(S);

    LL ans = 0;

    LL sum_c1=0;

    for(int i=0;i<n;++i){

         if(S[i]==c1){

             ++sum_c1;

         }

         if(S[i]==c2){

             for(int j=i;j>=i-K+2;j--){

                 if(j>=0&&S[j]==c1){//回溯算法要注意回溯的位置在数组范围内不能越界，因此j>=0 

                        ans--;

                  }

               }

               ans+=sum_c1;

         }

     }

     if(K>n){

         ans=0;

     }

     cout<<ans; 

     return 0;

}