LibreOJ NOIP Round #1 DNA 序列

题目链接

这道题刚开始我的思路就是暴力~~~~~

但是很无奈，TE了

我直接暴力出所有长度为n的子串

然后用EKMP算法算出子串的个数

这道题可以用空间来换时间

因为n很小

那么可以把所有碱基序列可能的情况都列出来

然后for循环一遍，把所有情况都统计一下

最后找出最大值~~~反正只用知道最多重复的个数，并不用知道碱基序列

况且这种方法也是可以反向找碱基序列的

那么如何把所有情况都列出来，而且不重不漏

类比一下哈希算法

可以把A 对应为0 ，G对应为1，C对应为2，T对应为3

这样就可以全部统计出来

#include"bits/stdc++.h"
using namespace std;
char ch[5000050],uk;
int k,n,x,us;
int mn[1200050];

int main()
{
    scanf("%s",ch+1);//从第二位开始输入字符串
    scanf("%d",&k);
    n=strlen(ch+1);//计算字符串的长度
    for(int i=1; i+k-1<=n; i++)//遍历所有可能的字符串的首字符
    {
        x=0;
        for(int j=i; j<=k+i-1; j++)
        {
            uk=ch[j];
            if(uk=='A')us=0;
            if(uk=='C')us=1;
            if(uk=='G')us=2;
            if(uk=='T')us=3;
            x=x*4+us;
        }
        mn[x]++;
    }
    int ans=0;
    for(int i=0; i<=1050000; i++)
    {
        ans=max(mn[i],ans);
    }
    printf("%d",ans);
    return 0;
}

原文链接：https://blog.csdn.net/wjhshuai/article/details/78461324