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;
}