LOJ537 - 「LibreOJ NOIP Round #1」DNA 序列

2017/11/05

题面

NOIP 复赛之前,HSD 桑进行了一项研究,发现人某条染色体上的一段 DNA 序列中连续的 k 个碱基组成的碱基序列与做 题的 AC 率有关!于是他想研究一下这种关系。现在给出一段 DNA 序列,请帮他求出这段 DNA 序列中所有连续 k 个碱 基形成的碱基序列中,出现最多的一种的出现次数。

代码

压位哈希。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int SIZ = 5e6 + 2007;

char buf[SIZ];
int N, K;
int cnt[1<<21];
int LUT[256];

int hashie(char s[16]) {
    int msk = 0;
    for(int i=0,p=0;i<K;i++,p+=2) {
        msk ^= LUT[s[i]]<<p;
    }

    return msk;
}

int main() {
    scanf("%s %d", buf+1, &K);
    N = strlen(buf+1);
    int ans = -1e9;

    LUT['A'] = 0;
    LUT['C'] = 1;
    LUT['T'] = 2;
    LUT['G'] = 3;

    for(int i=1;i+K-1<=N;i++) {
        char s[16];
        for(int j=0;j<K;j++) {
            s[j] = buf[i+j];
        }

        int pos = hashie(s);
        cnt[pos]++;
        ans = max(ans, cnt[pos]);
    }

    printf("%d\n", ans);
}