description
NOIP 复赛之前，HSD 桑进行了一项研究，发现人某条染色体上的一段 DNA 序列中连续的
k
k
k个碱基组成的碱基序列与做题的 AC 率有关！于是他想研究一下这种关系。现在给出一段 DNA 序列，请帮他求出这段 DNA 序列中所有连续
k
k
k个碱基形成的碱基序列中，出现最多的一种的出现次数。
n
≤
5
∗
1
0
6
,
k
≤
10
n\le5*10^6,k\le 10
n≤5∗106,k≤10
solution
直接找出所有连续
k
k
k个碱基形成的碱基序列的哈希值即可
code
#include<bits/stdc++.h>
using namespace std;
const int base=31;
const int mod=1e9+7;
const int N=5e6+10;
const int M=1e6+10;
char s[N];
int n,k,ans;
int t,hsh[N],pw[N];
vector<int>a[M],num[M];
inline void init(){
pw[0]=1;hsh[0]=0;for(int i=1;i<=n;++i) pw[i]=1ll*pw[i-1]*base%mod;
for(int i=1;i<=n;++i) hsh[i]=(1ll*hsh[i-1]*base%mod+(s[i]-'A'))%mod;
}
inline int gethsh(int l,int r){return (hsh[r]-1ll*hsh[l-1]*pw[r-l+1]%mod+mod)%mod;}
int main(){
scanf("%s%d",s+1,&k);
n=strlen(s+1);
init();
for(int i=1;i<=n-k+1;++i){
t=gethsh(i,i+k-1);
int u=t%M,flag=0;
for(int j=0;j<a[u].size();++j)
if(a[u][j]==t){
ans=max(ans,++num[u][j]);
flag=1;
break;
}
if(!flag){
a[u].push_back(t);
num[u].push_back(1);
}
}
printf("%d\n",ans);
return 0;
}
Processed:
0.010, SQL:
8
