7.12T1序列

1．序列

【问题描述】 Hzy 得到了一个字符串，这个字符串只有’A’,’G’,’C’,’T’这四种字符，她发现这个序列中连续 k 个字符可以形成一种新的字符序列，她称这种序列为 Hzy 序列，她现在想知道在所有的 Hzy 序列中，出现最多的一种的出现次数。

【输入格式】输入文件名为 uaena.in。输入文件的第一行为一个字符串，保证合法。输入文件的第二行为一个正整数 k。

【输出格式】输出文件名为 uaena.out。输出文件只有一个数，即所求答案。

【输入输出样例 1】

input

AAAAA

output

【样例解释 1】对于这段字符串中，连续的 k 个字符组成的 Hzy 序列只有 A，共出现 5 次，所以答案为 5。

【输入输出样例 2】

ueana.in

ACTCACTC

ueana.out

【样例解释 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=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

const ll Base=,Mod=;

int n,m,a[N];

char S[N];

inline int Check(char ch)

{

    if(ch=='A') return ;

    if(ch=='T') return ;

    if(ch=='C') return ;

    if(ch=='G') return ;

}

ll Seed[N];

inline void Pre(int n)

{

    int i;

    Seed[]=1ll; for(i=;i<=n;i++) Seed[i]=(ll)(Seed[i-]*%Mod);

}

struct Hash

{

    ll Hash[N];

    inline void Make(int n,int *a)

    {

        int i; Hash[]=; for(i=;i<=n;i++) Hash[i]=(Hash[i-]*%Mod+a[i])%Mod;

    }

    inline ll Ask(int l,int r)

    {

        return (ll)(Hash[r]+Mod-Hash[l-]*Seed[r-l+]%Mod)%Mod;

    }

    inline ll Get(int l,int r)

    {

        return Ask(l,r)*Seed[n-r]%Mod;

    }

}Ha;

int Sum[];

int main()

{

    freopen("ueana.in","r",stdin);

    freopen("ueana.out","w",stdout);

    int i,ans=;

    scanf("%s",S+); n=strlen(S+); R(m);

    for(i=;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+,i)]++;

    }

    for(i=;i<=Seed[m];i++) ans=max(ans,Sum[i]);

    Wl(ans);

    return ;

}

/*

input

AAAAA

1

output

5

input

ACTCACTC

4

output

2

*/

巴特西

7.12T1序列

最新文章

热门文章