fork download
copy 
  1. /* Look for:
  2. * the exact constraints (multiple sets are too slow for n=10^6 :( )
  3. * special cases (n=1?)
  4. * 1LL<<i and not 1<<i
  5. * overflow (ll vs ll?)
  6. * array bounds
  7. * if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
  8. */
  9.  
  10. // Author:: Subash Singha Roy
  11. // Institution:: Jalpaiguri Government Engineering College
  12.  
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15. #define ll long long
  16. #define dd double
  17. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  18. #define mod (ll)(998244353)
  19. #define sz(a) (ll)a.size()
  20. #define all(a) a.begin(),a.end()
  21. #define fr(i,a,b) for(ll i=a;i<b;i++)
  22. #define frr(i,a,b) for(ll i=a-1;i>=b;i--)
  23. #define pb emplace_back
  24. #define ee emplace
  25. #define rr return 0
  26. #define mp make_pair
  27. #define pr  pair <ll,ll>
  28. #define ff first
  29. #define ss second
  30. #define pie 3.1415926535898
  31. #define inf LLONG_MAX
  32. ll mult(ll a,ll b, ll p=mod){return ((a%p)*(b%p))%p;}
  33. ll add(ll a, ll b, ll p=mod){return (a%p + b%p)%p;}
  34. ll neg(ll a,ll p=mod){return (p-(a%p))%p;}
  35. ll sub(ll a,ll b,ll p=mod){return add(a,neg(b));}
  36. ll fpow(ll x, ll y)  
  37. {  
  38.     ll res = 1;     
  39.     x = x % mod; 
  40.     if (x == 0) return 0; 
  41.     while (y > 0)  
  42.     {  
  43.         if (y & 1LL)  
  44.             res = (res*x) % mod;  
  45.         y = y>>1LL;
  46.         x = (x*x) % mod;  
  47.     }  
  48.     return res;  
  49. }  
  50. ll inv(ll a, ll p = mod) {return fpow(a, p - 2);}
  51. bool sa(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second<b.second);}
  52. bool fd(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.first>b.first);}
  53. bool sd(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second>b.second);}
  54. ll dx[4]={0,0,1,-1};
  55. ll dy[4]={1,-1,0,0};
  56. bool valid(ll x,ll y,ll n,ll m){
  57.     if(x<0 || y<0){
  58.        return false;
  59.    }
  60.    else if(x>=n || y>=m){
  61.        return false;
  62.    }
  63.    else
  64.    return true;
  65. }
  66. #define maxn 500005 
  67.  
  68. vector<ll>v;
  69.  
  70. void findPrefix(string& t, ll m, ll pref[]){
  71.     ll len=0;
  72.     pref[0]=0;
  73.     for(ll i=1;i<m;i++){
  74.         if(t[i]==t[len]){
  75.             len++;
  76.             pref[i]=len;
  77.         }
  78.         else{
  79.             if(len!=0){
  80.                 len = pref[len-1];
  81.                 i--;
  82.             }
  83.             else{
  84.                 pref[i]=0;
  85.             }
  86.         }
  87.     }
  88. }
  89.  
  90. void KMP(string &s, string &t){
  91.     ll n,m,i=0,j=0;
  92.     n=(ll)s.length();
  93.     m=(ll)t.length();
  94.     ll pref[m];
  95.     findPrefix(t,m,pref);
  96.     while(i<n){
  97.         if(s[i]==t[j]){
  98.             i++;j++;
  99.         }
  100.         if(j == m){
  101.             v.pb(i-j);
  102.             j = pref[j-1];
  103.         }
  104.         else if(i<n && s[i]!=t[j]){
  105.             if(j!=0){
  106.                 j=pref[j-1];
  107.             }
  108.             else{
  109.                 i++;
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. int main(){
  116.     fio
  117.     ll T;
  118.     T = 1;
  119.     // cin >>T;
  120.     fr(tc,1,T+1){
  121.         // cout<<"Case #"<<t<<": ";
  122.         ll q;
  123.         string s,t;
  124.         cin>>s;
  125.         cin>>q;
  126.         while(q--){
  127.             cin>>t;
  128.             v.clear();
  129.             KMP(s,t);
  130.             cout<<(ll)v.size()<<" ";
  131.             fr(i,0,(ll)v.size()){
  132.                 cout<<v[i]<<" ";
  133.             }
  134.             cout<<"\n";
  135.         }
  136.     }
  137.     rr;
  138. }
  139.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
BABABBAAABBAAABBAAAA AABBBBBAAAAABBBBABAAAAAABBABBAABABAABABBBAAAAABAAB BBAABABABBABBBAABBBA BABABBABBAAAABBBABAABABBA BBAABAABBB AAABBBABAAAABBB BBAABAAABBBABBAAABABABABAABABBBAAAAABAAB
stdout
copy 
Standard output is empty
https://ideone.com/8rONJ6
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

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!