2017 计蒜之道 初赛 第一场 B.阿里天池的新任务

该文被密码保护

    

  

 

 

 

          

  

 

 

 

2017 计蒜之道 初赛 第一场 B.阿里天池的新任务

  

/* QYP kuai wo dai ma*/
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<ctime>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define ll long long
#define re register
using namespace std;
const int N=1e6;
int w[N+10];
int n,a,b,L,R;
char s[N+10],t[N+10];
int nxt[N+10];
inline int gi() {
    re int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res;
}
void get_w() {
    w[1]=b;
    for(re int i=2;i<=n;i++) w[i]=(w[i-1]+a)%n;
}
void get_s() {
    for(re int i=1;i<=n;i++) {
        if(w[i]>=L&&w[i]<=R) {
            if(w[i]%2==0) s[i]='A';
            else s[i]='T';
        }
        else {
            if(w[i]%2==0) s[i]='G';
            else s[i]='C';
        }
    }
}
void NEXT() {
    int len=strlen(t+1);
    nxt[1]=0;
    int j=0;
    for(re int i=2;i<=len;i++) {
        while(j&&t[j+1]!=t[i]) j=nxt[j];
        if(t[j+1]==t[i]) nxt[i]=++j;
    }
}
void KMP() {
    int lens=strlen(s+1),j=0;
    int lent=strlen(t+1);
    int ans=0;
    for(re int i=1;i<=lens;++i) {
        while(j&&t[j+1]!=s[i]) j=nxt[j];
        if(t[j+1]==s[i]) ++j;
        if(j==lent) {ans++;j=nxt[j];}
    }
    cout<<ans;
}
int main() {
    freopen("2.in","r",stdin);
    freopen("2.out","w",stdout);
    n=gi(),a=gi(),b=gi(),L=gi(),R=gi();
    s[0]='@',t[0]='$';
    scanf("%s",t+1);
    get_w();
    get_s();
    NEXT();
    KMP();
    return 0;
}