Language: C++

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
#endif // _MSC_VER
template<class V> struct SparseTable { // [L,R)
	const V def = 0;
	inline V comp(V a, V b) { return min(a, b); }

	int n; vector<V> a, b[22]; inline int __lg(int x) { return 32 - 1 - __builtin_clz(x); }
	void init(vector<V> v) {
		int nn = v.size(); n = 1; while (n < nn) n *= 2; a.resize(n);
		rep(i, 0, 22) b[i].resize(n); rep(i, 0, nn) a[i] = v[i];

		int d = 1 << __lg(n - 1), e = d << 1;
		for (int h = 0, f; (f = 1 << h) <= d; ++h) {
			for (int i = f, r = f << 1; i < e; i += r) {
				b[h][i - 1] = a[i - 1];
				for (int j = i - 2; j >= i - f; --j) b[h][j] = comp(b[h][j + 1], a[j]);
				b[h][i] = a[i];
				for (int j = i + 1; j < i + f; ++j) b[h][j] = comp(b[h][j - 1], a[j]);
			}
		}
	}

	V get(int L, int R) {
		assert(0 <= L && L <= R); if (L == R)return def; R--; if (L == R)return a[L]; int h = __lg(L ^ R);
		return comp(b[h][L], b[h][R]);
	}
};
struct SuffixArraySAIS {
	vector<int> sa, lcp, rank;
	SparseTable<int> rmq;
	SuffixArraySAIS() {}
	SuffixArraySAIS(string str_) : str(str_) {
		init(str_);
	}
	void init(string str_) {
		str = str_;
		N = str.size() + 1;
		S = vector<int>(N, 0);
		for (int i = 0; i < N; i++) S[i] = str[i];
		A_SIZE = 256;

		buildSA();
		buildLCP();
		buildRMQ();
	}
	string str;
	vector<int> S;
	int A_SIZE;
	int N;
	vector<int> t, B;
	enum { STYPE, LTYPE };

	inline bool is_lms(int i) {
		return i > 0 && t[i] == STYPE && t[i - 1] == LTYPE;
	}
	void bucket() {
		B = vector<int>(A_SIZE);
		for (int i = 0; i < N; i++) B[S[i]]++;
		for (int i = 0; i < A_SIZE - 1; i++) B[i + 1] += B[i];
	}
	void induced_sort() {
		bucket();
		for (int i = 0; i < N; i++) {
			int j = sa[i] - 1;
			if (j >= 0 && S[j] >= S[j + 1]) sa[B[S[j] - 1]++] = j;
		}
		bucket();
		for (int i = N; i--; ) {
			int j = sa[i] - 1;
			if (j >= 0 && S[j] <= S[j + 1]) sa[--B[S[j]]] = j;
		}
	}
	void buildSA() {
		N = S.size();
		sa.assign(N, -1);
		if (N == 1) {
			sa[0] = 0;
			return;
		}
		t.assign(N, STYPE);
		for (int i = N - 1; i--;)
			if (S[i] > S[i + 1] || (S[i] == S[i + 1] && t[i + 1] == LTYPE))
				t[i] = LTYPE;
		bucket();
		for (int i = N; i--;)
			if (is_lms(i)) sa[--B[S[i]]] = i;
		induced_sort();

		int N1 = 0;
		for (int i = 0; i < N; i++) if (is_lms(sa[i])) sa[N1++] = sa[i];

		fill(sa.begin() + N1, sa.end(), -1);
		int name = 0, prev = -1;
		for (int i = 0; i < N1; i++) {
			int cur = sa[i];
			bool diff = (prev == -1);
			for (int j = 0; !diff; j++) {
				if (j > 0 && is_lms(cur + j)) break;
				if (S[cur + j] != S[prev + j]) diff = true;
			}
			if (diff) name++;
			sa[N1 + cur / 2] = name - 1;
			prev = cur;
		}
		vector<int> S1, sa1(N1);
		for (int i = N1; i < N; i++) if (sa[i] >= 0) S1.push_back(sa[i]);
		if (name == N1) for (int i = 0; i < N1; i++) sa1[S1[i]] = i;
		else sa1 = SuffixArraySAIS(S1, name, false).sa;

		N1 = 0;
		for (int i = 0; i < N; i++) if (is_lms(i)) S1[N1++] = i;
		for (int i = 0; i < N1; i++) sa1[i] = S1[sa1[i]];

		fill(sa.begin(), sa.end(), -1);
		bucket();
		for (int i = N1; i--;) {
			int j = sa1[i];
			sa[--B[S[j]]] = j;
		}
		induced_sort();
	}
	void buildLCP() {
		rank.resize(N);
		lcp.resize(N - 1);
		for (int i = 0; i < N; i++) rank[sa[i]] = i;
		int h = 0;
		for (int i = 0; i < N - 1; i++) {
			int j = sa[rank[i] - 1];
			if (h > 0) h--;
			for (; j + h < N && i + h < N && S[j + h] == S[i + h]; h++);
			lcp[rank[i] - 1] = h;
		}
	}

	void buildRMQ() {
		rmq.init(lcp);
	}
	int common_prefix(int x, int y) {
		if (x == y) return N - 1 - x;
		if (y >= N - 1) return 0;
		if (rank[x] > rank[y]) swap(x, y);
		return rmq.get(rank[x], rank[y]);
	}
	int compare(int x, int xn, int y, int yn) {
		int l = common_prefix(x, y);
		if (l >= xn || l >= yn) return xn < yn ? -1 : xn == yn ? 0 : 1;
		return rank[x] < rank[y] ? -1 : x == y ? 0 : 1;
	}
};
// トポロジカルソートする O(n)
// 返り値が true の時のみ意味を持つ(false の場合は閉路)
struct TopologicalSort {
    vector<vector<int>> E; TopologicalSort(int N) { E.resize(N); }
    void add_edge(int a, int b) { E[a].push_back(b); }
    bool visit(int v, vector<int>& order, vector<int>& color) { color[v] = 1;
        for (int u : E[v]) { if (color[u] == 2) continue; if (color[u] == 1) return false;
        if (!visit(u, order, color)) return false; } order.push_back(v); color[v] = 2; return true; }
    bool sort(vector<int> &order) { int n = E.size(); vector<int> color(n);
        for (int u = 0; u < n; u++) if (!color[u] && !visit(u, order, color)) return false;
        reverse(order.begin(), order.end()); return true; } };
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/














string S, T;
int NS, NT;
int dp[2010101];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S >> T;
	string s = S;
	while (S.length() < T.length()) S += s;
	NS = S.length();
	NT = T.length();

	string match = S + S + "#" + T;
	SuffixArraySAIS sais(match);
	TopologicalSort ts(NS);
	
	rep(i, 0, NS) {
		if (sais.common_prefix(i, NS * 2 + 1) == NT) {
			ts.add_edge(i, (i + NT) % NS);
		}
	}

	vector<int> ord;
	bool res = ts.sort(ord);
	if (res == false) {
		cout << -1 << endl;
		return;
	}

	int ans = 0;
	fore(cu, ord) {
		chmax(ans, dp[cu]);
		fore(to, ts.E[cu]) chmax(dp[to], dp[cu] + 1);
	}
	cout << ans << endl;
}







Compiler output:
a.cc: In member function 'void SuffixArraySAIS::buildSA()':
a.cc:120:59: error: no matching function for call to 'SuffixArraySAIS::SuffixArraySAIS(std::vector<int>&, int&, bool)'
  120 |                 else sa1 = SuffixArraySAIS(S1, name, false).sa;
      |                                                           ^
a.cc:44:9: note: candidate: 'SuffixArraySAIS::SuffixArraySAIS(std::string)'
   44 |         SuffixArraySAIS(string str_) : str(str_) {
      |         ^~~~~~~~~~~~~~~
a.cc:44:9: note:   candidate expects 1 argument, 3 provided
a.cc:43:9: note: candidate: 'SuffixArraySAIS::SuffixArraySAIS()'
   43 |         SuffixArraySAIS() {}
      |         ^~~~~~~~~~~~~~~
a.cc:43:9: note:   candidate expects 0 arguments, 3 provided
a.cc:40:8: note: candidate: 'SuffixArraySAIS::SuffixArraySAIS(const SuffixArraySAIS&)'
   40 | struct SuffixArraySAIS {
      |        ^~~~~~~~~~~~~~~
a.cc:40:8: note:   candidate expects 1 argument, 3 provided
a.cc:40:8: note: candidate: 'SuffixArraySAIS::SuffixArraySAIS(SuffixArraySAIS&&)'
a.cc:40:8: note:   candidate expects 1 argument, 3 provided