阿里天池的新任务（简单）(KMP统计子串出现的次数)

阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列 tt，判断它在另一个根据规则生成的 DNA 碱基序列 ss 中出现了多少次。

输出格式

输出一个整数，为 tt 在 ss 中出现的次数。

样例说明

对于第一组样例，生成的 ss 为TTTCGGAAAGGCC。

样例输入1

13 2 5 4 9
AGG

样例输出1

1

样例输入2

103 51 0 40 60
ACTG

样例输出2

5

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;char s[];
int w1,w2;
char t[];
int nextt[];void getnext(int lent)
{
    int i=,j=-;
    nextt[i]=-;
    while(i<lent) {
        if(j==-||t[i]==t[j]) {
            nextt[++i]=++j;
        }
        else j=nextt[j];
    }
}int kmp(int pos,int lent,int lens)
{
    int i=pos,j=,ans=;
    while(i<lens) {
        if(s[i]==t[j]||j==-) ++i,++j;
        else j=nextt[j];
        if(j==lent) {
            ans++;
            j=nextt[j-];
            i--;
        }
    }
    return ans;
}int main()
{
    int n,a,b,l,r;
    scanf("%d %d %d %d %d",&n,&a,&b,&l,&r);
    //scanf("%s",t);
    cin>>t;
    w1=b;
    int cous=;
    if(b>=l&&b<=r&&b%==){
            s[cous++]='A';
        }else if(b>=l&&b<=r&&b%==){
            s[cous++]='T';
        }else if(b<l&&b%==||b>r&&b%==){
            s[cous++]='G';
        }else if(b<l&&b%==||b>r&&b%==){
            s[cous++]='C';
        }
    for(int i=;i<n;i++){
        w2=w1+a;
        w2%=n;
        if(w2>=l&&w2<=r&&w2%==){
            s[cous++]='A';
        }else if(w2>=l&&w2<=r&&w2%==){
            s[cous++]='T';
        }else if(w2<l&&w2%==||w2>r&&w2%==){
            s[cous++]='G';
        }else if(w2<l&&w2%==||w2>r&&w2%==){
            s[cous++]='C';
        }
        w1=w2;
    }
    int ans=;
    int lens=strlen(s);
    int lent=strlen(t);
    getnext(lent);
    ans=kmp(,lent,lens);
    printf("%d\n",ans);
    return ;
}