题目描述
NOIP 复赛之前，HSD 桑进行了一项研究，发现人某条染色体上的一段 DNA 序列中连续的 kkk 个碱基组成的碱基序列与做题的 AC 率有关！于是他想研究一下这种关系。
现在给出一段 DNA 序列，请帮他求出这段 DNA 序列中所有连续 kkk 个碱基形成的碱基序列中，出现最多的一种的出现次数。
输入格式
两行，第一行为一段 DNA 序列，保证 DNA 序列合法，即只含有 A, G, C, T 四种碱基；
第二行为一个正整数 kkk，意义与题目描述相同。
输出格式
一行，一个正整数，为题目描述中所求答案。
样例
样例输入 1
AAAAA
1样例输出 1
5样例解释 1
对于这段 DNA 序列，连续的 111 个碱基组成的碱基序列只有 A，共出现 555 次，所以答案为 555。
样例输入 2
ACTCACTC
4样例输出 2
2样例解释 2
对于这段 DNA 序列，连续的 444 个碱基组成的碱基序列为：ACTC, CTCA, TCAC 与 CACT。其中 ACTC 出现 222 次，其余均出现 111 次，所以出现最多的次数为 222，即为答案。
数据范围与提示
记 DNA 序列长度为 nnn。
本题共 101010 组数据，只有输出与标准输出一致才可以获得该测试点的分数。
下面给出每组数据的范围和满足性质情况：
| 111 | =105=10 ^5=105 | =1=1=1 | 满足性质 |
| 2,32,32,3 | ≤5×105\le 5 \times 10 ^5≤5×105 | =1=1=1 | - |
| 444 | ≤5×105\le 5 \times 10 ^5≤5×105 | ≤10\le 10≤10 | 满足性质 |
| 5,6,7,85,6,7,85,6,7,8 | ≤106\le 10 ^6≤106 | ≤10\le 10≤10 | - |
| 9,109,109,10 | =5×106=5 \times 10 ^6=5×106 | =10=10=10 | - |
性质：给出的 DNA 碱基序列中每个碱基均相同。
对于所有数据均保证 k≤nk\le nk≤n
思路分析 ： hash 拉链即可解决
代码示例：
using namespace std;
#define ll unsigned long long
const ll maxn = 5e6+5;
const ll mm = 200007; char s[maxn];
ll k, len;
ll p = 19873;
ll hash_[maxn], pp[maxn]; void init_hash() {
hash_[0] = 0; pp[0] = 1;
for(ll i = 1; i <= len; i++) {
hash_[i] = hash_[i-1]*p + (s[i]-'a');
pp[i] = pp[i-1]*p;
}
}
struct node
{
ll x;
ll cnt = 0;
int next; //!!!
}arr[maxn];
int head[mm+50];
ll tot = 1; ll _max(ll a, ll b){
return a>b?a:b;
}
void solve() {
ll ans = 1;
memset(head, -1, sizeof(head));
for(ll i = k; i <= len; i++){
ll num = hash_[i]-hash_[i-k]*pp[k];
ll num2 = num%mm;
int f = head[num2];
int sign = 0;
while(f != -1) {
if (arr[f].x == num) {
arr[f].cnt++;
ans = _max(ans, arr[f].cnt);
sign = 1;
break;
}
f = arr[f].next;
}
if (sign) continue;
arr[tot].x = num;
arr[tot].cnt = 1;
arr[tot].next = head[num2];
head[num2] = tot++;
}
printf("%lld\n", ans);
} int main() { scanf("%s", s+1);
len = strlen(s+1);
scanf("%llu", &k);
init_hash();
solve();
return 0;
}