https://ac.nowcoder.com/acm/problem/15253
太简单了,直接上代码吧!
#include <iostream> #include <cstring> #include <cmath> #include <stdio.h> #include <cstdlib> #include <algorithm> #include <vector> #include <set> #include <map> #include <iomanip> #define rep(i,a,b) for(int i = a; i <= b ; i ++ ) #define pre(i,a,b) for(int i = b ; i >= a ; i --) #define ll long long #define inf 0x3f3f3f3f #define ull unsigned long long #define ios ios::sync_with_stdio(false),cin.tie(0) using namespace std; typedef pair<int,int> PII ; const int N = 2e6 + 10 ; ull base[N]; ull hs[N]; char T[N],s[N]; vector<ull> v; ull n; ull gethash(int i,int j){//get hash of [i,j] return hs[j]-hs[i-1]*base[j-i+1]; } bool judge(int i,int j){ ull x=gethash(i,j);//the part of son's hash int id=lower_bound(v.begin(),v.end(),x)-v.begin();//found of two found if(id==v.size())return false;//if not found else return v[id]==x; //judge whether be found } int main() { ios; base[0] =1 ; for(int i = 1 ; i < N ; i ++) base[i]= base[i-1]*131; cin>>(T+1); ull lent=strlen(T+1); for(int i=1;i<=lent;i++) T[i+lent]=T[i];// one plus for(int i=1;i<=2*lent;i++) hs[i]=hs[i-1]*131+(T[i]-'a'+1); for(int i=1;i<=lent;i++) v.push_back(gethash(i,i+lent-1)); sort(v.begin(),v.end());//sort the result of hash cin>>n; while(n--) { cin>>(s+1); ull lens=strlen(s+1); int cnt=0; for(int i=1;i<=lens;i++){ hs[i]=hs[i-1]*131+(s[i]-'a'+1);//do hash } for(int i=1;i+lent-1<=lens;i++){ if(judge(i,i+lent-1)){ cnt++; } } cout<<cnt<<endl; } return 0; }