Submission #6652689

---

Source Code Expand

#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

Judge Result