fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pii pair <int, int>
  5. #define fi first
  6. #define se second
  7. const int MAXN=  1e5+5;
  8. const int MOD = 1e9+7;
  9. const int base = 29;
  10. int n, lx, ly, kpk, px[MAXN], py[MAXN], p[MAXN];
  11. string x, y;
  12. vector <int> ans;
  13. bool sama (int ix, int iy, int len){
  14.     int prefx = (px[ix+len] - px[ix]+ MOD)%MOD;
  15.     int prefy = (py[iy+len] - py[iy] + MOD ) % MOD;
  16.     if (ix > iy){
  17.         prefy = prefy*p[ix-iy]%MOD;
  18.     }
  19.     else if( iy > ix){
  20.         prefx = prefx*p[iy-ix]%MOD;
  21.  
  22.     }
  23.     return prefx == prefy;
  24. }
  25.  
  26. signed main(){
  27.     ios_base:: sync_with_stdio(false);
  28.     cin.tie(nullptr); cout.tie(nullptr);
  29.     // ubah string ke angka dengan pangkat 29 (prefix sum)
  30.     cin >> n >> x >> y;
  31.     lx = x.size();
  32.     ly = y.size();
  33.     kpk = (ly*lx)/__gcd(lx,ly);
  34.  
  35.     p[0] =1;
  36.     // x
  37.     for (int i =0; i < lx; i++){
  38.         p[i+1] = p[i]*base%MOD;
  39.         px[i+1] = ((x[i]-'a'+1)*p[i]+px[i]) %MOD;
  40.     }
  41.     // y
  42.     for (int i =0; i < ly; i++){
  43.         p[i+1] = p[i]*base%MOD;
  44.         py[i+1] = ((y[i]-'a'+1)*p[i]+py[i]) %MOD;
  45.     }
  46.     // cari angka pertama yang salah
  47.     int i =0;
  48.     while( i <kpk && ans.size() < n){
  49.         int ix = i %lx, iy = i %ly;
  50.         int l =1, r = min(lx-ix, ly-iy);
  51.         if (sama (ix, iy, r)){
  52.             i+= r;
  53.             continue;
  54.         }
  55.         int res = r;
  56.         // yang panjang r udah di cek diatas
  57.         r--;
  58.         while( l <= r){
  59.             int mid = (l +r)/2;
  60.             if (sama(ix, iy, mid)){
  61.                 l = mid +1;
  62.  
  63.             }
  64.             // cari yang beda pertama
  65.             else {
  66.                  r= mid -1;
  67.                  res = mid;
  68.             }
  69.         }
  70.  
  71.         ans.push_back(i+res-1);
  72.         i += res;
  73.     }
  74.  
  75.     if (ans.empty()){
  76.         for (int i =0; i < n; i++){
  77.             cout << -1 << endl;
  78.             return 0;
  79.          }
  80.     }
  81.     int sz = ans.size();
  82.     for (int i =0; i < n; i++){
  83.         cout << ans[i%sz] + kpk * (i /sz) << endl;
  84.     }
  85. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
abca
abc
stdout
copy 
4
5
https://ideone.com/nXHXQa
language:
C++ (gcc 8.3)
created:
9 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!