Submission #8238154

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

string s, t;
void check_Inf(string s, string t){
	//1 char
	set<char> set_s, set_t;
	for(auto c:s) set_s.insert(c);
	for(auto c:t) set_t.insert(c);
	if ((int) set_s.size() == 1 && (int)set_t.size() == 1 
		&& *set_s.begin() == *set_t.begin()) {
		cout << -1 << endl;
		exit(0);
	}
	if (s.length() < t.length()) swap(s, t);
	string tmp = t;
	while(t.length() < s.length()) t += tmp;
	if (t == s) {
		cout << -1 << endl;
		exit(0);
	}

}
int main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	cin >> s >> t; check_Inf(s, t);
	string tmp_s = s;
	while(s.length() < t.length()) s += tmp_s;
	int n = s.length(), m = t.length();
	string t_s = t + '_' + s + s;
	//z-function
	int len = t_s.length();
	vector<int> z(len, 0);
	z[0] = 0;
	int x = 0, y = 0;
	for(int i=1; i<len; i++){
		z[i] = max(0, min(z[i-x], y-i+1));
		while(i+z[i] < len && t_s[i+z[i]] == t_s[z[i]]) {
			x = i, y = i+z[i], z[i]++;
		}
	}

	vector<int> cnt(len+5, 0);
	int ans = 0;
	for(int i=m+1; i<len; i++){
		if (z[i] == m) {
			cnt[i] = 1 + cnt[i-m];
			ans = max(ans, cnt[i]);
		}
	}
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result