1．序列
【问题描述】 Hzy 得到了一个字符串，这个字符串只有’A’,’G’,’C’,’T’这四种字符，她发现这个 序列中连续 k 个字符可以形成一种新的字符序列，她称这种序列为 Hzy 序列，她现在想知 道在所有的 Hzy 序列中，出现最多的一种的出现次数。
【输入格式】 输入文件名为 uaena.in。 输入文件的第一行为一个字符串，保证合法。 输入文件的第二行为一个正整数 k。
【输出格式】 输出文件名为 uaena.out。 输出文件只有一个数，即所求答案。
【输入输出样例 1】
input
AAAAA
1
output
5
【样例解释 1】 对于这段字符串中，连续的 k 个字符组成的 Hzy 序列只有 A，共出现 5 次，所以答案 为 5。
【输入输出样例 2】
ueana.in
ACTCACTC
4
ueana.out
2
【样例解释 1】 对于这段字符串中，连续的 k 个字符组成的 Hzy 序列有 ACTC，CTCA，TCAC，CACT 其中 ACTC 共出现 2 次，其余只出现了 1 次， 所以答案为 2。
【数据规模与规定】
n<=5 × 10^6 k<=10
sol: 哈希一下，O(n）水过
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘\n‘) const int N=5000005; const ll Base=4,Mod=19260817; int n,m,a[N]; char S[N]; inline int Check(char ch) { if(ch==‘A‘) return 0; if(ch==‘T‘) return 1; if(ch==‘C‘) return 2; if(ch==‘G‘) return 3; } ll Seed[N]; inline void Pre(int n) { int i; Seed[0]=1ll; for(i=1;i<=n;i++) Seed[i]=(ll)(Seed[i-1]*4%Mod); } struct Hash { ll Hash[N]; inline void Make(int n,int *a) { int i; Hash[0]=0; for(i=1;i<=n;i++) Hash[i]=(Hash[i-1]*4%Mod+a[i])%Mod; } inline ll Ask(int l,int r) { return (ll)(Hash[r]+Mod-Hash[l-1]*Seed[r-l+1]%Mod)%Mod; } inline ll Get(int l,int r) { return Ask(l,r)*Seed[n-r]%Mod; } }Ha; int Sum[3000005]; int main() { freopen("ueana.in","r",stdin); freopen("ueana.out","w",stdout); int i,ans=0; scanf("%s",S+1); n=strlen(S+1); R(m); for(i=1;i<=n;i++) a[i]=Check(S[i]); Pre(n); Ha.Make(n,a); for(i=m;i<=n;i++) { // cout<<i-m+1<<‘ ‘<<i<<‘ ‘<<Ha.Ask(i-m+1,i)<<‘ ‘<<Ha.Get(i-m+1,i)<<endl; Sum[Ha.Ask(i-m+1,i)]++; } for(i=0;i<=Seed[m];i++) ans=max(ans,Sum[i]); Wl(ans); return 0; } /* input AAAAA 1 output 5 input ACTCACTC 4 output 2 */
原文：https://www.cnblogs.com/gaojunonly1/p/11178501.html
