fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef unsigned long long ull;
  6. typedef long long ll;
  7. typedef pair<int, int> ii;
  8. typedef vector<ii> vii;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11.  
  12. #define PI (2*acos(0.0))
  13. #define eps 1e-9
  14. #define pb push_back
  15. #define endl "\n"
  16. #define watch(x) cout << (#x) << " is " << (x) << endl;
  17. #define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
  18. #define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
  19. #define ff first
  20. #define ss second
  21. #define fu cout << "lol" << endl;
  22. #define precision(n) cout << fixed << setprecision(n);
  23. #define lb lower_bound
  24. #define up upper_bound
  25. #define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
  26. #define all(a) a.begin(), a.end()
  27. #define min3(a,b,c) min(a,min(b,c))
  28. #define max3(a,b,c) max(a,max(b,c))
  29. #define mem(a,val) memset(a,val,sizeof(a))
  30. #define loop(i,n) for(i = 0; i < n; i++)
  31. #define TC ull T; cin>>T; while(T--)
  32. #define IN(x) {scanf("%d",&x);}
  33. #define LL(x) {scanf("%lld",&x);}
  34. #define CC(x) {scanf("%c",&x);}
  35. #define pfl(x) printf("%d\n",x)
  36. #define pfll(x) printf("%lld\n",x)
  37. #define newl puts("")
  38. #define space printf(" ")
  39. #define MOD 1000000007
  40. #define speed ios_base::sync_with_stdio(false); cin.tie(NULL);
  41.  
  42. vector<int> prefix_function(string s) {
  43.     int n = (int)s.length();
  44.     vector<int> pi(n);
  45.     for (int i = 1; i < n; i++) {
  46.         int j = pi[i-1];
  47.         while (j > 0 && s[i] != s[j])
  48.             j = pi[j-1];
  49.         if (s[i] == s[j])
  50.             j++;
  51.         pi[i] = j;
  52.     }
  53.     return pi;
  54. }
  55.  
  56. int main()
  57. {
  58.     speed;
  59.     int i = 0, j = 0, cs = 0, in;
  60.     string s, t; cin>>s>>t;
  61.     int sz = s.size();
  62.     s += s;
  63.     vi lps = prefix_function(s);
  64.     i = 0, j = 0;
  65.     vi pos;
  66.     while(i < s.size()){
  67.         if(t[j] == s[i]) j++,i++;
  68.         if(j == t.size()){
  69.             if(i - j + 1 <= sz) pos.pb(i-j+1);  // t occurs starting at (i-j+1) <= sz
  70.             j = lps[j-1];
  71.         }
  72.         else if(i < s.size() && t[j] != s[i]){
  73.             if(j) j = lps[j-1];
  74.             else i++;
  75.         }
  76.     }
  77.     int N = s.size();
  78.     vi pre(N+5);
  79.     for(i = 0; i < pos.size(); i++){
  80.         int x = pos[i] + t.size() - 1; // S = s+s, t occurs in the 1st s
  81.         pre[x]++;
  82.         x = pos[i] + sz + t.size() - 1; // t occurs in the 2nd s
  83.         if(x <= N) pre[x]++; // must not end in 3rd s so <= N
  84.     }
  85.     for(i = 1; i <= N; i++) pre[i] = pre[i-1]+pre[i];
  86.     int q; cin>>q;
  87.     while(q--){
  88.         int n; cin>>n;
  89.         int ans = 0;
  90.         if(n/sz - 1 > 0) ans += (n/sz - 1) * (int)pos.size(), n-= (n/sz - 1)*sz;
  91.         ans += pre[n];
  92.         cout << ans << endl;
  93.     }
  94.     return 0;
  95. }
Runtime error #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WM7PB7
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!