当前位置:首页 > 瞎暴力 > 计蒜客 阿里天池的新任务(简单)

计蒜客 阿里天池的新任务(简单)

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

首先,定义一个序列 w


\displaystyle w_{i} = \begin{cases}b, & i = 0\\(w_{i-1} + a) \mod n, & i > 0\end{cases}


接下来,定义长度为 n 的 DNA 碱基序列 s(下标从 0 开始):


\displaystyle s_{i} = \begin{cases}A , & (L \le w_{i} \le R) \land (w_{i}\ \mathrm{mod}\ 2 = 0)\\T , & (L \le w_{i} \le R) \land (w_{i}\ \mathrm{mod}\ 2 = 1)\\G , & ((w_{i} < L) \lor (w_{i} > R)) \land (w_{i}\ \mathrm{mod}\ 2 = 0)\\C , & ((w_{i} < L) \lor (w_{i} > R)) \land (w_{i}\ \mathrm{mod}\ 2 = 1)\end{cases}


其中 \land 表示“且”关系,\lor 表示“或”关系,a\ \mathrm{mod}\ b 表示 a 除以 b 的余数。

现给定另一个 DNA 碱基序列 t,以及生成 s 的参数 n , a , b , L , R,求 t在 s 中出现了多少次。

输入格式

数据第一行为 5 个整数,分别代表 n , a , b , L , R。第二行为一个仅包含ATGC的一个序列 t

数据保证 0 < a < n, 0 \le b < n,0 \le L \le R < n, |t| \le 10^{6}a,n 互质。

对于简单版本,1 \leq n \leq 10^{6}

对于中等版本,1 \leq n \leq 10^{9}, a = 1

对于困难版本,1 \leq n \leq 10^{9}

输出格式

输出一个整数,为 t 在 s 中出现的次数。

样例说明

对于第一组样例,生成的 sTTTCGGAAAGGCC

样例输入1

13 2 5 4 9
AGG

样例输出1

1

样例输入2

103 51 0 40 60
ACTG

样例输出2

5
#include<stdio.h>
#include<string.h>
const int N=1000005;
int Next[N];
char o[N],s[N];

void getnext(int n)
{
    int k=-1,i=0;
    Next[0]=-1;
    while(i<n)
    {
        if(k==-1||o[i]==o[k])
        {
            i++;k++;Next[i]=k;
        }else k=Next[k];
    }
}

void kmp(int n,int m)
{
    int i=0,j=0,ans=0;
    while(i<n)
    {
        if(s[i]==o[j]) i++,j++;
        else if(j==0) i++;
        else j=Next[j];
        if(j==m)
        {
            ans++;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    int n,a,b,l,r;
    scanf("%d %d %d %d %d",&n,&a,&b,&l,&r);
    scanf("%s",o);
    b-=a;
    for(int i=0;i<n;i++)
    {
        b=(b+a)%n;
        if( b>=l&&b<=r&&(b%2==0) )
            s[i]='A';
        else if( b>=l&&b<=r&&(b%2==1) )
            s[i]='T';
        else if( ((b<l)||(b>r))&&(b%2==0) )
            s[i]='G';
        else if( ((b<l)||(b>r))&&(b%2==1) )
            s[i]='C';
    }
    int ol=strlen(o);
    getnext(ol);
    kmp(n,ol);
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=459

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。