阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列
t
，判断它在另一个根据规则生成的 DNA 碱基序列
s
中出现了多少次。
首先，定义一个序列
w
：
w
i
=
{
b
,
(
w
i
−
1
+
a
)
m
od
n
,
i
=
0
i
>
0
接下来，定义长度为
n
的 DNA 碱基序列
s
（下标从
0
开始）：
s
i
=
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
A
,
T
,
G
,
C
,
(
L
≤
w
i
≤
R
)
∧
(
w
i
m
o
d
2
=
0
)
(
L
≤
w
i
≤
R
)
∧
(
w
i
m
o
d
2
=
1
)
(
(
w
i
<
L
)
∨
(
w
i
>
R
)
)
∧
(
w
i
m
o
d
2
=
0
)
(
(
w
i
<
L
)
∨
(
w
i
>
R
)
)
∧
(
w
i
m
o
d
2
=
1
)
其中
∧
表示“且”关系，
∨
表示“或”关系，
a
m
o
d
b
表示
a
除以
b
的余数。
现给定另一个 DNA 碱基序列
t
，以及生成
s
的参数
n
,
a
,
b
,
L
,
R
，求
t
在
s
中出现了多少次。
输入格式
数据第一行为
5
个整数，分别代表
n
,
a
,
b
,
L
,
R
。第二行为一个仅包含
A
、
T
、
G
、
C
的一个序列
t
。
数据保证
0
<
a
<
n
,
0
≤
b
<
n
,
0
≤
L
≤
R
<
n
,
∣
t
∣
≤
1
0
6
，
a
,
n
互质。
对于简单版本，
1
≤
n
≤
1
0
6
；
对于中等版本，
1
≤
n
≤
1
0
9
,
a
=
1
；
对于困难版本，
1
≤
n
≤
1
0
9
。
输出格式
输出一个整数，为
t
在
s
中出现的次数。
样例说明
对于第一组样例，生成的
s
为
TTTCGGAAAGGCC
。
样例输入1
13 2 5 4 9 AGG
样例输出1
1
样例输入2
103 51 0 40 60 ACTG
样例输出2
5
#include"iostream"
#include"cstring"
#define MAXX 1000000+5
using namespace std;
int w[MAXX];
char s[MAXX],t[MAXX];
int total=0;
void makeNext(char *pat,int next[])
{
int len=strlen(pat),k=0,cur=1;
next[0]=0;
for(;cur<len;cur++)
{
while(k>0&&pat[k]!=pat[cur]) k=next[k-1];
if(pat[k]==pat[cur]) k++;
next[cur]=k;
}
}
void kmp(char *str,char *pat,int next[])
{
makeNext(pat,next);
int str_len=strlen(str);
int pat_len=strlen(pat);
int k=0,cur=0;
while(cur<str_len)
{
while(k>0&&pat[k]!=str[cur])k=next[k-1];
if(pat[k]==str[cur]) k++;
if(k==pat_len)
{
total++;
}
cur++;
}
}
int main()
{
int n,a,b,l,r;
int next[MAXX];
cin>>n>>a>>b>>l>>r;
cin>>t;
for(int i=0;i<n;i++)
{
if(i==0)
w[i]=b;
else
w[i]=(w[i-1]+a)%n;
if((w[i]>=l&&w[i]<=r)&&w[i]%2==0)
s[i]='A';
else if((w[i]>=l&&w[i]<=r)&&w[i]%2==1)
s[i]='T';
else if((w[i]<l||w[i]>r)&&w[i]%2==0)
s[i]='G';
else if((w[i]<l||w[i]>r)&&w[i]%2==1)
s[i]='C';
}
kmp(s,t,next);
cout<<total;
}