首页 > 代码库 > HDU 4821 2013长春现场赛hash

HDU 4821 2013长春现场赛hash

2024-10-30 20:44:02   211人阅读

题意：

一个字符串S  问其中有几个子串能满足以下条件：

1、长度为M*L

2、可以被分成M个L长的小串  每个串都不一样

分析：

hash方法，一个种子base，打表出nbase[i]表示base的i次方

将以i位字符开头之后的串hash成一个无符号长整型：hash[i]=hash[i+1]*base+str[i]-‘a‘+1

然后每个L长度的小串的hash值即为：hash[i]-hash[i+L]*nbase[L]

map记录hash值的个数

以i位字符开头的字符串与以i+L位字符开头的字符串只相差两个地方，减去hash[i ~ i+L]，加上hash[i+M*L ~ i+(M+1)*L]

这样算节省了很多时间

#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int maxn=100005;char str[maxn];ull shash[maxn],nbase[maxn],base=31;map<ull,int>mp;int main(){//    freopen("in.txt","r",stdin);    int M,L;    nbase[0]=1;    for(int i=1;i<maxn;i++)        nbase[i]=nbase[i-1]*base;    while(~scanf("%d%d",&M,&L))    {        scanf("%s",str);        int n=strlen(str);        shash[n]=0;        for(int i=n-1;i>=0;i--)            shash[i]=shash[i+1]*base+str[i]-‘a‘+1;        int ans=0;        for(int i=0;i<L && i+M*L<=n;i++)        {            mp.clear();            for(int j=i;j<i+M*L;j+=L)                mp[shash[j]-shash[j+L]*nbase[L]]++;            if(mp.size()==M) ans++;            for(int j=i+L;j+M*L<=n;j+=L)            {                ull tmp=shash[j-L]-shash[j]*nbase[L];                mp[tmp]--;                if(mp[tmp]==0) mp.erase(tmp);                mp[shash[j+(M-1)*L]-shash[j+M*L]*nbase[L]]++;                if(mp.size()==M) ans++;            }        }        printf("%d\n",ans);    }    return 0;}

 

HDU 4821 2013长春现场赛hash


联系
我们