fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mag 100000
  5. #define inf 1e18
  6. #define MOD 1000000007
  7. #define rep(i,n) for(i=0;i<n;i++)
  8. #define mset(x,v) memset(x, v, sizeof(x))
  9. #define print_array(a,n) for(i=0;i<n;i++) cout<<a[i]<<" ";
  10. #define var_val(x) cout<<#x<<" "<<x<<endl;
  11. #define pb push_back
  12. #define fe first
  13. #define se second
  14.  
  15. vector<ll> z_algo(string s )
  16. {
  17.     ll L = 0, R = 0;
  18.     ll n=s.size();
  19.     vector<ll>z(n);
  20.     for (ll i = 1; i < n; i++)
  21.     {
  22.         if (i > R)
  23.         {
  24.             L = R = i;
  25.             while (R < n && s[R-L] == s[R]) R++;
  26.             z[i] = R-L;
  27.             R--;
  28.         }
  29.         else
  30.         {
  31.             ll k = i-L;
  32.             if (z[k] < R-i+1) z[i] = z[k];
  33.             else
  34.             {
  35.                 L = i;
  36.                 while (R < n && s[R-L] == s[R]) R++;
  37.                 z[i] = R-L;
  38.                 R--;
  39.             }
  40.         }
  41.     }
  42.     return z;
  43. }
  44.  
  45. int main()
  46. {
  47.     string s,s1;
  48.     cin>>s>>s1;
  49.     string S=s1+"$"+s;
  50.     vector<ll>z=z_algo(S);
  51.     ll n=s.size();
  52.     ll n1=s1.size();
  53.     ll i;
  54.  
  55.     bool flag=0;
  56.     for(i=n1+n; i>=n1+1; i--)
  57.     {
  58.         if(z[i]>=n1)
  59.         {
  60.             flag=1;
  61.             if(z[i-n1]==n1)
  62.             {
  63.                 z[i-n1]+=z[i];
  64.                 z[i]=0;
  65.             }
  66.         }
  67.     }
  68.  
  69.     if(flag==0)
  70.         cout<<-1;
  71.     else
  72.     {
  73.         for(i=n1+n; i>=n1+1; i--)
  74.         {
  75.             if(z[i]>=n1)
  76.             {
  77.                 printf("%d %d\n",i-n1,z[i]/n1);
  78.             }
  79.         }
  80.     }
  81.  
  82.  
  83. }
  84.  
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/thSLKc
language:
C++14 (gcc 8.3)
created:
7 years 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!