题目描述
NOIP 复赛之前,HSD 桑进行了一项研究,发现人某条染色体上的一段 DNA 序列中连续的 kkk 个碱基组成的碱基序列与做题的 AC 率有关!于是他想研究一下这种关系。现在给出一段 DNA 序列,请帮他求出这段 DNA 序列中所有连续 kkk 个碱基形成的碱基序列中,出现最多的一种的出现次数。
输入格式
两行,第一行为一段 DNA 序列,保证 DNA 序列合法,即只含有 A
, G
, C
, T
四种碱基;
输出格式
一行,一个正整数,为题目描述中所求答案。
样例
样例输入 1
AAAAA1
样例输出 1
5
样例解释 1
对于这段 DNA 序列,连续的 111 个碱基组成的碱基序列只有 A
,共出现 555 次,所以答案为 555。
样例输入 2
ACTCACTC4
样例输出 2
2
样例解释 2
对于这段 DNA 序列,连续的 444 个碱基组成的碱基序列为:ACTC
, CTCA
, TCAC
与 CACT
。其中 ACTC
出现 222 次,其余均出现 111 次,所以出现最多的次数为 222,即为答案。
数据范围与提示
记 DNA 序列长度为 nnn。本题共 101010 组数据,只有输出与标准输出一致才可以获得该测试点的分数。
下面给出每组数据的范围和满足性质情况:
测试点编号 | nnn | kkk | 其他 |
---|---|---|---|
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 longconst 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;}