Untitled
typedef unordered_map<ll, bool> umii; typedef unordered_set<int, int> umsii; const ll mod = 1e9 + 7; const int inf = (int) 1e5 + 5; const int base = (int) 131; const ll m2 = 1LL * mod * mod; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; string s1, s2; umii mp; ll h1[inf], h2[inf], p[inf]; int n; void nhap() { cin >> s1 >> s2; } bool check(int len) { int cnt = 0; FORD(i, 1, n) { ll cur = h1[i + len - 1] - h1[i - 1] * p[len] + m2; mp[cur] = 1; } FORD(i, 1, n) { ll cur = h2[i + len - 1] - h2[i - 1] * p[len] + m2; if(mp[cur]) cnt++; } return cnt >= 1; } void solve() { nhap(); n = s1.size(); s1 = " " + s1 + s1; s2 = " " + s2 + s2; h1[0] = h2[0] = 0; p[0] = 1; FORD(i, 1, n * 2) p[i] = p[i - 1] * base; FORD(i, 1, n * 2) { h1[i] = h1[i - 1] * base + s1[i]; h2[i] = h2[i - 1] * base + s2[i]; } int l = 1, r = n, res = 0; while(r - l >= 0) { int m = l + (r - l) / 2; if(check(m)) { res = m; l = m + 1; } else { r = m - 1; } } cout << res; }
Leave a Comment