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

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

时间&空间

2000ms

262144K

题目描述

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

首先,定义一个序列 ww:

![]()

接下来,定义长度为 nn 的 DNA 碱基序列 ss(下标从 00 开始):
​​
![]()

其中 ∧ 表示“且”关系,∨ 表示“或”关系,a mod b 表示 a 除以 b 的余数。

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

输入格式

数据第一行为 55 个整数,分别代表 n,a,b,L,R 第二行为一个仅包含A、T、G、C的一个序列 t。

数据保证 0 < a < n,0≤b<n, 0≤L≤R<n ,∣t∣≤10^6 a,n 互质。

对于简单版本,1≤n≤10^6

对于中等版本 a = 1 1≤n≤10^9

对于困难版本 1≤n≤10^9

输出格式

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

样例说明

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

样例输入1

13 2 5 4 9
AGG

样例输出1

1

样例输入2

103 51 0 40 60
ACTG

样例输出2

5

AC代码

#include <stdio.h>
#include <string.h>

int w1;
int n,a,b,L,R;
int fff=0;
int next1[1000009];
int sum=0;
char sumstr[1000009];
char x[1000009];
int cc;
inline int getw(int i)
{
    if(i==0)
    {
        w1=b;
        return w1;
    }
    else
    {
    w1 = (w1+a)%n;
    return w1;
    }
}
inline void Next(char b[])
//部分匹配表的实现
{
    int i,j;
    i=0;
    j=-1;
    next1[i]=j;   //匹配表初值
    while(i<strlen(b))
    {
        if(j==-1||b[i]==b[j])
        {
            i++;
            j++;
            next1[i]=j;
        }
        else
            j=next1[j];
    }
    return ;
}

inline int KMP(char a[],char b[])//kmp匹配算法
{
    int i,j;
    i=j=0;
    Next(b);//先计算部分匹配表
    while(i<sum)
    {
        if(j==-1||a[i]==b[j])
        {

            i++;
            j++;
            if(j==cc)
            fff++;//找到目标字符串,返回到主程序。
        }
        else
            j=next1[j];//a[i]与b[j]不匹配,查表需要跳过的字符个数。
    }
    return -1;//没有找到返回-1
}
int main()
{
    scanf("%d%d%d%d%d",&n,&a,&b,&L,&R);
    for(int i=0;i<n;i++)
    {
        getw(i);
        if((L<=w1&&w1<=R))
        {
            if(w1%2==0)
            sumstr[sum]='A';
            else
            sumstr[sum]='T';

            sum++;
        }
        else
        if((L>w1||w1>R))
        {
            if(w1%2==0)
            sumstr[sum]='G';
            else
            sumstr[sum]='C';
            sum++;
        }
    }
    sumstr[sum]=0;
    scanf("%s",x);
    cc=strlen(x);
    KMP(sumstr,x);
    printf("%d\n",fff);

    return 0;
}

结语

这一题别人直接KMP都过了,我还需要用内联函数再过为什么???
私以为是我用了太多的全局变量

发表评论