Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * author: MySakure
- * created: 23.10.2019 19:48:14
- **/
- #include<bits/stdc++.h>
- using namespace std;
- #define ull unsigned long long
- const int maxn=1e6+10;
- int n;
- string s;
- ull hashs[maxn],hash1[maxn],bin[maxn];
- ull p=233;
- int ans=0;
- multiset<ull>st;
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- #ifdef mysakure
- freopen("in1.txt","r",stdin);
- #endif
- cin>>s;
- int len=s.size();
- for(int i=1;i<=len;++i)hash1[i]=hash1[i-1]*p+s[i-1]-'a';
- st.insert(hash1[len]);
- bin[0]=1;
- for(int i=1;i<=maxn;++i)bin[i]=bin[i-1]*p;
- for(int i=1;i<=len;++i){
- st.insert((hash1[len]-hash1[i]*bin[len-i])*bin[i]+hash1[i]);
- }
- cin>>n;
- while(n--){
- cin>>s;
- ans=0;
- int l=s.size();
- for(int i=1;i<=l;++i){
- hashs[i]=hashs[i-1]*p+s[i-1]-'a';
- }
- for(int i=1;i+len-1<=l;++i){
- if(st.count(hashs[i+len-1]-hashs[i-1]*bin[len])){
- ++ans;
- }
- }
- cout<<ans<<'\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement