首页 > 代码库 > HDU 4821 2013长春现场赛hash
HDU 4821 2013长春现场赛hash
题意:
一个字符串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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。