链接:
@[toc]
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld
题目描述
白兔有一个字符串T。白云有若干个字符串S1,S2..Sn。
白兔想知道,对于白云的每一个字符串,它有多少个子串是和T循环同构的。
提示:对于一个字符串a,每次把a的第一个字符移动到最后一个,如果操作若干次后能够得到字符串b,则a和b循环同构。
所有字符都是小写英文字母
输入描述:
第一行一个字符串T(|T|<=10^6)
第二行一个正整数n (n<=1000)
接下来n行为S1~Sn (|S1|+|S2|+…+|Sn|<=10 ^ 7),max(|S1|,|S2|,|S3|,|S4|,..|Sn|)<=10 ^ 6
输出描述:
输出n行表示每个串的答案
示例1
输入
abab 2 abababab ababcbaba
输出
5 2
题解:
hash题
好久没打都忘得差不多了
讲哈希的博客
根据题意,我们可以得知,要寻找与T是循环同构的子串
那T也就相当于是环,我们拆环为链,长度加倍,
然后将二倍的T中每一部分取哈希,每一部分的长度就是原T的长度
然后根据大小进行排序
输入子串a后,因为是在中取连续子串,所以本身就是一条链,我们按照T的长度对a的每一部分取hash然后比较是否相等
比较大小的方法可以用二分查找,因为我们之前已经对大小进行排序了;也可以模拟map,直接用map会超时
代码:
因为我的代码写太乱了,找了大佬条理清晰的代码。
并加上详细注释(应该很详细了 )
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 5; ull hs[maxn]; ull base[maxn]; char T[maxn<<1],s[maxn]; int n; vector<ull> v; ull gethash(int i,int j){//获得子串的hash return hs[j]-hs[i-1]*base[j-i+1]; } //查找 bool judge(int i,int j){ ull x=gethash(i,j);//获得子串的hash int id=lower_bound(v.begin(),v.end(),x)-v.begin();//二分查找 if(id==v.size())return false;//如果没找到 else return v[id]==x;//判断是否找到 } int main(){ base[0]=1; for(int i=1;i<maxn;i++) base[i]=base[i-1]*131; cin>>(T+1); ll len=strlen(T+1); for(int i=1;i<=len;i++) T[i+len]=T[i];//拆环为链,长度加倍 for(int i=1;i<=2*len;i++) hs[i]=hs[i-1]*131+(T[i] - 'a' + 1);//对链进行hash for(int i=1;i<=len;i++) v.push_back(gethash(i,i+len-1));//获得子串的hash sort(v.begin(),v.end());//对哈希结果进行排序 ,方便后面的二分查找 cin>>n; while(n--){ cin>>(s+1); ll lens=strlen(s+1); int cnt=0; for(int i=1;i<=lens;i++) hs[i]=hs[i-1]*131+(s[i] - 'a' + 1);//进行hash for(int i=1;i+len-1<=lens;i++) if(judge(i,i+len-1))cnt++;//判断子串是否与T循环同构 cout<<cnt<<endl; } return 0; }