Submission #6652689


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

const int MAX = 500000, MS = 2;
const long long mod[] = {999999937LL, 1000000007LL}, base = 9973;
struct rolling_hash {
    int n;
    vector<long long> hs[MS], pw[MS];
    rolling_hash(){}
    rolling_hash(const string &s) {
        n = s.size();
        for (int i = 0; i < MS; i++) {
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            for (int j = 0; j < n; j++) {
                pw[i][j+1] = pw[i][j]*base%mod[i];
                hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
            }
        }
    }

    long long hash(int l, int r, int i) { return ((hs[i][r]-hs[i][l]*pw[i][r-l])%mod[i]+mod[i])%mod[i]; }

    bool match(int l1, int r1, int l2, int r2) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l1,r1,i)==hash(l2,r2,i);
        return ret;
    }

    bool match(int l, int r, long long h[]) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l,r,i)==h[i];
        return ret;
    }
};

class UnionFind {
 public:
     int n;
     std::vector<int> par;
     std::vector<int> num;

     explicit UnionFind(int n) {  // [0 n)のunion find
         this->n = n;
         this->par.resize(n);
         this->num.resize(n, 1);
         for (int i = 0; i < n; i++) {
             this->par[i] = i;
         }
     }

     int root(int i) {
         if (par[i] == i)
             return i;
         else
             return par[i] = root(par[i]);
     }

     bool same(int i, int j) {
         return root(i) == root(j);
     }

     // もしすでに、くっ付いていたら-1を返す
     int unite(int i, int j) {
         int t = root(i);
         int k = root(j);

         if (t == k)
            return -1;

         par[t] = k;
         num[k] += num[t];
         return 0;
     }

     int size(int i) {
         return num[root(i)];
     }
};

signed main() {
  string s,t;
  cin>>s>>t;
  ll N = s.size();
  ll NT = t.size();
  string p="";
  while(p.size() < 3*NT || p.size() < 3*N){
    p += s;
  }
  s = p;
  vector<bool> ok(N, false);
  //cout<<"s="<<s<<endl;
  //cout<<"t="<<t<<endl;
  auto rh = rolling_hash(t+s);

  for (int i=0; i<N; i++) {
    //cout<<0<<" " << t.size()+i << " " << sa.prefixCommonLength(0, t.size()+i) << endl;
    //if(lh.prefixCommonLength(0, NT+i) >= NT ){
    if (rh.match(0, NT, NT+i, 2*NT+i)){
      ok[i%N] = true;
    }
  }


  auto uf = UnionFind(N);
  rep(i,0,N){
    if (ok[i] && ok[(i+NT)%N]){
      ll res = uf.unite(i, (i+NT)%N);
      if (res == -1){
        cout<<-1<<endl;
        return 0;
      }
    }
  }

  ll ans = 0;
  for (int i=0;i<N;i++) {
    if (ok[i])
      ans = max(ans, (ll)uf.size(i));
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task F - Strings of Eternity
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3038 Byte
Status
Exec Time 217 ms
Memory 89424 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 600 / 600 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56, b57, b58, b59, b60, b61, b62, b63, b64, b65, b66, b67, b68, b69, b70
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 1 ms 256 KB
b10 1 ms 256 KB
b11 1 ms 256 KB
b12 182 ms 68656 KB
b13 217 ms 89424 KB
b14 190 ms 68664 KB
b15 125 ms 66824 KB
b16 153 ms 57372 KB
b17 178 ms 68664 KB
b18 179 ms 68664 KB
b19 154 ms 57244 KB
b20 178 ms 68664 KB
b21 203 ms 84816 KB
b22 202 ms 84816 KB
b23 209 ms 87120 KB
b24 146 ms 54044 KB
b25 178 ms 68664 KB
b26 145 ms 53788 KB
b27 203 ms 84816 KB
b28 207 ms 86300 KB
b29 203 ms 84944 KB
b30 204 ms 84816 KB
b31 202 ms 84816 KB
b32 178 ms 68664 KB
b33 178 ms 68664 KB
b34 178 ms 68664 KB
b35 203 ms 84816 KB
b36 159 ms 60840 KB
b37 178 ms 68664 KB
b38 178 ms 68664 KB
b39 202 ms 84816 KB
b40 178 ms 68664 KB
b41 178 ms 68792 KB
b42 202 ms 84816 KB
b43 203 ms 85200 KB
b44 179 ms 69180 KB
b45 203 ms 84816 KB
b46 202 ms 84816 KB
b47 182 ms 68792 KB
b48 159 ms 60840 KB
b49 179 ms 68664 KB
b50 179 ms 68664 KB
b51 203 ms 84816 KB
b52 179 ms 68664 KB
b53 203 ms 84816 KB
b54 178 ms 68664 KB
b55 179 ms 68664 KB
b56 139 ms 52636 KB
b57 141 ms 52524 KB
b58 32 ms 11708 KB
b59 3 ms 896 KB
b60 37 ms 13880 KB
b61 12 ms 4312 KB
b62 22 ms 9212 KB
b63 139 ms 52636 KB
b64 178 ms 68664 KB
b65 178 ms 68664 KB
b66 202 ms 84816 KB
b67 202 ms 84944 KB
b68 178 ms 68664 KB
b69 178 ms 68664 KB
b70 202 ms 84816 KB