阿里天池的新任务(简单)KMP,看样子网上有bug的kmp算法还是有蛮多

2017年05月21日 6点热度 0人点赞 0条评论

https://nanti.jisuanke.com/t/15500

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

首先,定义一个序列 ww

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

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

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}
si=A,T,G,C,(LwiR)(wi mod 2=0)(LwiR)(wi mod 2=1)((wi<L)(wi>R))(wi mod 2=0)((wi<L)(wi>R))(wi mod 2=1)

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

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

输入格式

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

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

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

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

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

输出格式

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

样例说明

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

样例输入1

13 2 5 4 9
AGG

样例输出1

1

样例输入2

103 51 0 40 60
ACTG

样例输出2

5

//应该说是单纯的KMP吧
//我定义个next数组都有歧义 
#include
#include
#include
using namespace std;
const int mx=1000100;
int n,a,b,L,R;
char s[mx];
char t[mx];
int Next[mx];
void getNext(){
	int i=0,k=-1,len=strlen(t);
	Next[0]=-1;
	while(iR)
		if(w&1) s[i]='C';
		else s[i]='G';
		else if(w&1) s[i]='T';
		else s[i]='A';
		w=(w+a)%n;
	}
	s[n]=0;
	//cout<
未经允许不得转载!阿里天池的新任务(简单)KMP,看样子网上有bug的kmp算法还是有蛮多

update

纸上得来终觉浅, 绝知此事须躬行。