Description
Input
Output
Sample Input
Sample Input1
AAAAA
1
Sample Input2
ACTCACTC
4
Sample Output
Sample Output1
5
【样例 1 解释】
对于这段 DNA 序列，连续的 1 个碱基组成的碱基序列只有 A，共出现 5 次，所以答案为 5。
Sample Output2
2
【样例 2 解释】
对于这段 DNA 序列，连续的 4 个碱基组成的碱基序列为：ACTC, CTCA, TCAC 与CACT。其中 ACTC 出现 2 次，其余均出现 1 次，所以出现最多的次数为 2，即为答案。
Data Constraint
Solution
转成4进制标记数组即可。
Code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 5000004
using namespace std;
I k,x,a[N],len,f[13],ans;
I bz[N<<1];
char c;
I main(){
freopen("dna.in","r",stdin);
freopen("dna.out","w",stdout);
c=getchar();
while(c<'A'||c>'T') c=getchar();
while(c>='A'&&c<='T'){
len++;
a[len]=c=='A'?0:(c=='C'?1:(c=='G'?2:3));
c=getchar();
}
f[0]=f[1]=1;
F(i,2,10) f[i]=f[i-1]*4;
k=x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}
F(i,1,k-1) x=x*4+a[i];
F(i,k,len){
x=(x-f[k]*(x/f[k]))*4+a[i];
ans=max(ans,++bz[x]);
}
printf("%d\n",ans);
return 0;
}
