牛客竞赛——白兔的字符串(字符串hash)

博客学习：https://blog.csdn.net/MyLinChi/article/details/79509455 and https://blog.csdn.net/MyLinChi/article/details/79508112

 题目链接：https://ac.nowcoder.com/acm/problem/15253

 一涉及循环字符串就要想到扩展加倍字符串

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int seed=131;
ull hs[N],pw[N];
char T[N<<1],s[N];
vector<ull> v;
//初始化hash权值pw；pw[i]=seed^i;
void init_pw(){pw[0]=1;for(int i=1;i<N;i++){pw[i]=pw[i-1]*seed;}
}
//O(1)复杂度子串s[i:j]的hash值(通过hash值的相等判断两个子串相等)
ull gethash(int i,int j){return hs[j]-hs[i-1]*pw[j-i+1];//自然溢出
}
//查找
bool judge(int i,int j){ull x=gethash(i,j);int id=lower_bound(v.begin(),v.end(),x)-v.begin();if(id==v.size())return false;else return v[id]==x;
}
int main()
{IOS;init_pw();cin>>(T+1);ll len=strlen(T+1);hs[0]=1;//加倍模式串for(int i=1;i<=len;i++){T[i+len]=T[i];}//计算前缀hashfor(int i=1;i<=2*len;i++){hs[i]=hs[i-1]*seed+T[i];}//计算子串T[i:i+len-1]的hash值，加入vectorfor(int i=1;i<=len;i++){v.push_back(gethash(i,i+len-1));}sort(v.begin(),v.end());//排序便于后续查找int n;cin>>n;while(n--){cin>>(s+1);ll lens=strlen(s+1);int cnt=0;//计算s的前缀hash值for(int i=1;i<=lens;i++){hs[i]=hs[i-1]*seed+s[i];}//查找有多少个子串s[i:i+len-1]是否在vector中for(int i=1;i+len-1<=lens;i++){if(judge(i,i+len-1))cnt++;}cout<<cnt<<endl;}getchar();getchar();return 0;
}