#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
int min_cyc(const string &s) {
int n = s.size();
int res = 0;
for (int l = 0; l < n; ){
res = l;
int r = l, p = l + 1;
for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|
{
char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo
if (s[r] > c) break;
if (s[r] < c) r = l - 1;
}
l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx + sy) cases
}
return res;
}
struct Hash {
static constexpr i64 P = 1E12 + 7, M = 29;
int n;
i64 x;
Hash(std::string s) : n(s.size()) {
for (int i = 0; i < n; i++)
x = (1LL * x * M + (s[i] - 'a' + 1)) % P;
}
i64 get(int l, int r) {
return x;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
string a, b;
cin >> a >> b;
int lo = 0, hi = std::min(a.size(), b.size()) + 1;
auto work = [&](string a, int x) {
int n = a.size();
vector<pair<i64, int>> b;
for (int i = 0; i <= n - x; i++) {
string s = a.substr(i, x);
int p = min_cyc(s);
rotate(s.begin(), s.begin() + p, s.end());
b.emplace_back(Hash(s).get(0, x), i);
reverse(s.begin(), s.end());
p = min_cyc(s);
rotate(s.begin(), s.begin() + p, s.end());
b.emplace_back(Hash(s).get(0, x), i);
}
sort(b.begin(), b.end());
return b;
};
auto get = [&](int len) -> pair<int, int> {
auto x = work(a, len);
auto y = work(b, len);
int i = 0;
for (auto [a, b] : x) {
while (i + 1 < int(y.size()) && y[i].first < a) i++;
if (y[i].first == a) {
return {b, y[i].second};
}
}
return {-1, -1};
};
while (lo + 1 < hi) {
int m = (lo + hi) / 2;
if (get(m).first != -1) {
lo = m;
} else {
hi = m;
}
}
std::cout << lo << "\n";
auto x = get(lo);
std::cout << x.first << " " << x.second << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
