AtCoder Beginner Contest 135

E Golf

參考

F Strings of Eternity

題意： 給定字元串S，T，求最多可将T複制多少次的形成的串，還存在一個j，使得S複制j次之後形成的字元串還包含T複制i次的串

分析：

1. 考慮字元串比對，首先先想到KMP比對
2. 考慮怎麼能求最大次數呢，分析樣例可知，可以将串複制以後接上去，這樣啟發我們先複制 ∣ S ∣ + ∣ T ∣ |S|+|T| ∣S∣+∣T∣長度的串，然後以T為母串，求KMP，對于比對并且可以互相轉移(在模 ∣ M ∣ |M| ∣M∣域上相同)建立節點, 拓撲排序求最長路，如果有環，說明 ∞ \infin ∞

const int maxn = 1e6 + 10;
char ar[maxn], br[maxn];
int f[maxn];
bool sign[maxn];
void getFail(char *P, int *f) {
	int m = strlen(P);
	f[0] = f[1] = 0;
	for (int i = 1; i < m; ++i) {
		int j = f[i];
		while (j && P[i] != P[j]) j = f[j];
		f[j + 1] = P[i] == P[j] ? j + 1 : 0;
	}
}
void Find(char *T, char *P, int *f) {
	int n = strlen(T), m = strlen(P);
	getFail(P, f);
	int j = 0;
	for (int i = 0; i < n; ++i) {
		while (j && T[i] != P[j]) j = f[j];
		j = T[i] == P[j] ? j + 1 : 0;
		if (j == m) {
			sign[i - m + 1] = 1;
		}
	}
}

vector<int> G[maxn];
int  vis[maxn];
int q[maxn];
int cnt = 0;
int dp[maxn];
void dfs(int u) {
	vis[u] = 1;
	for (auto c : G[u]) {
		if (vis[c] == 2) continue;
		if (vis[c] == 1) {
			cout << -1 << endl;
			exit(0);
		}
		dfs(c);
	}
	vis[u] = 2;
	q[++cnt] = u;
}
int main(void)
{
	cin >> ar >> br;
	int n = strlen(ar);
	int m = strlen(br);
	int nn = n;
	while (n < nn + m) {
		for (int i = 0; i < nn; ++i)
			ar[n++] = i;
	}
	ar[n] = '\0';
	Find(ar, br, f);
	for (int i = 0; i < n; ++i) {
		if (sign[i]) {
			// cout << i << " " << (i + m) % nn << endl;
			G[i].Pb((i + m) % nn);
		}
	}
	// DEBUG;
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	assert(cnt == n);
	int ans = 0;
	for (int i = n; i >= 1 ; --i) {
		int t = q[i];
		for (auto c : G[t]) {
			dp[c] = max(dp[c], dp[t] + 1);
			ans = max(ans, dp[c]);
		}
	}
	cout << ans << endl;



	return 0;
}