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;
}