Submission #6588977


Source Code Expand

Copy
#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_);
	}
	SuffixArraySAIS(const vector<int>& S_, int A_SIZE_, bool lcp_flag = true) : S(S_), A_SIZE(A_SIZE_) {
		buildSA();
		if (lcp_flag) {
			buildLCP();
			buildRMQ();
		}
	}
	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;
}





Submission Info

Submission Time
Task F - Strings of Eternity
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 7018 Byte
Status AC
Exec Time 721 ms
Memory 503668 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 70
Set Name Test Cases
Sample a01, a02, a03
All 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 AC 1 ms 256 KB
a02 AC 1 ms 256 KB
a03 AC 2 ms 256 KB
b04 AC 1 ms 256 KB
b05 AC 1 ms 256 KB
b06 AC 1 ms 256 KB
b07 AC 1 ms 256 KB
b08 AC 1 ms 256 KB
b09 AC 1 ms 256 KB
b10 AC 1 ms 256 KB
b11 AC 1 ms 256 KB
b12 AC 295 ms 251320 KB
b13 AC 578 ms 503668 KB
b14 AC 306 ms 263480 KB
b15 AC 299 ms 251236 KB
b16 AC 194 ms 158040 KB
b17 AC 271 ms 239672 KB
b18 AC 273 ms 239672 KB
b19 AC 195 ms 163672 KB
b20 AC 267 ms 239672 KB
b21 AC 511 ms 468340 KB
b22 AC 512 ms 470260 KB
b23 AC 565 ms 482328 KB
b24 AC 187 ms 147612 KB
b25 AC 287 ms 239720 KB
b26 AC 176 ms 144472 KB
b27 AC 523 ms 470352 KB
b28 AC 530 ms 474760 KB
b29 AC 578 ms 461844 KB
b30 AC 569 ms 473544 KB
b31 AC 578 ms 468180 KB
b32 AC 400 ms 239704 KB
b33 AC 370 ms 236656 KB
b34 AC 379 ms 239744 KB
b35 AC 721 ms 470896 KB
b36 AC 331 ms 234440 KB
b37 AC 271 ms 239620 KB
b38 AC 286 ms 239708 KB
b39 AC 529 ms 470244 KB
b40 AC 283 ms 239624 KB
b41 AC 272 ms 239632 KB
b42 AC 525 ms 470240 KB
b43 AC 527 ms 464216 KB
b44 AC 282 ms 239628 KB
b45 AC 562 ms 474252 KB
b46 AC 558 ms 468484 KB
b47 AC 287 ms 236920 KB
b48 AC 274 ms 235388 KB
b49 AC 299 ms 239688 KB
b50 AC 297 ms 239632 KB
b51 AC 556 ms 461724 KB
b52 AC 301 ms 239628 KB
b53 AC 592 ms 472748 KB
b54 AC 299 ms 239700 KB
b55 AC 300 ms 235900 KB
b56 AC 185 ms 136252 KB
b57 AC 189 ms 135544 KB
b58 AC 39 ms 32460 KB
b59 AC 3 ms 2176 KB
b60 AC 77 ms 57616 KB
b61 AC 19 ms 15092 KB
b62 AC 42 ms 30676 KB
b63 AC 190 ms 135684 KB
b64 AC 317 ms 239632 KB
b65 AC 281 ms 239672 KB
b66 AC 651 ms 470748 KB
b67 AC 612 ms 470280 KB
b68 AC 319 ms 239644 KB
b69 AC 293 ms 239716 KB
b70 AC 575 ms 470268 KB