LibreOJ NOIP Round 1 DNA 序列 字符串哈希

#include <bits/stdc++.h>
#define MAXN 5000005
#define MAXM 1050000
using namespace std;
char ch[MAXN];
int cnt[MAXN];
const int val[26]={0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0};
//打一个表 A:0 T:1 C:2 G:3
const char st[4]={'A','T','C','G'};
int main(){
	int n=0;
	while (true){
		char c=getchar();
		if (c=='\n') break;
		else ch[++n]=c;
	}
	int k;
	scanf("%d",&k);
	for (register int i=1;i<=n-k+1;++i){
		int ans=0;
		for (register int j=i;j<=i+k-1;++j){
			ans=ans*4+val[ch[j]-'A'];
		}
		cnt[ans]++;
	}
	int maxn=0;
	for (register int i=0;i<MAXM;++i){
		if (cnt[i]>maxn) maxn=cnt[i];
	}
	printf("%d\n",maxn);
}

#include <bits/stdc++.h>
#define MAXN 5000005
#define MAXM 1050000
using namespace std;
int ch[MAXN],cnt[MAXN];
const int val[26]={0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0};
int main(){
	int n=0;
	while (true){
		char c=getchar();
		if (c=='\n') break;
		else ch[++n]=val[c-'A'];
	}
	int k;
	scanf("%d",&k);
    int now=0;
    int pw=1;
    for (register int i=1;i<=k;++i){
        now=now*4+ch[i];
        pw*=4;
    }
    cnt[now]++;
	for (register int i=2;i<=n-k+1;++i){
		now-=ch[i-1]*pw/4;
        now*=4;
        now+=ch[i+k-1];
        cnt[now]++;
	}
	int maxn=0;
	for (register int i=0;i<MAXM;++i){
		if (cnt[i]>maxn) maxn=cnt[i];
	}
	printf("%d\n",maxn);
}