#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define bug(...)
#endif
#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;
ar<int, 3> solve(const string& S, const string& T) {
int N = sz(S), M = sz(T);
// vector dpL(N, vi(M)), dpR(N, vi(M));
vi rollL(M), rollR(M);
vi c(N + M), cc(N + M), ii(N + M);
for (int d = -(N - 1); d < M; d++) {
// vector<pi> ij;
for (int i = 0; i < N; i++) {
int j = i + d;
if (0 <= j && j < M) {
ii[N + d] = i;
// ij.push_back({i, j});
}
}
/*
reverse(all(ij));
int c = 0;
for (auto [i, j] : ij) {
if (S.at(i) == T.at(j)) c++;
else c = 0;
if (c) {
int x = i + c - 1, y = j + c - 1;
cerr << x << ' ';
// bug(i, j, x, y, c);
dpL.at(x).at(j) = max(dpL.at(x).at(j), c);
dpR.at(i).at(y) = max(dpR.at(i).at(y), c);
}
}
cerr << endl;
*/
}
/*
for (int j = 0; j < M; j++) for (int i = N - 1; i > 0; i--)
dpL.at(i - 1).at(j) = max(dpL.at(i - 1).at(j), dpL.at(i).at(j) - 1);
for (int i = 0; i < N; i++) for (int j = M - 1; j > 0; j--)
dpR.at(i).at(j - 1) = max(dpR.at(i).at(j - 1), dpR.at(i).at(j) - 1);
*/
ar<int, 3> best{0, 0, 0};
for (int i = N; i >= 0; i--) {
if (i) {
for (int j = 0; j < M; j++) {
rollL.at(j)--;
rollL[j] = max(rollL[j], 0);
}
for (int d = -(N - 1); d < M; d++) {
int i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0);
while (0 <= j && j < M && i_ + c_ - 1 == i - 1) {
rollL.at(j) = max(rollL.at(j), c_);
ii[N + d]--;
cc[N + d] = c_;
i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0);
}
}
}
fill(all(rollR), 0);
if (i < N) {
for (int d = -(N - 1); d < M; d++) {
int j = i + d;
if (0 <= j && j < M) {
if (S[i] == T[j]) c[N + d]++;
else c[N + d] = 0;
if (c[N + d]) {
int y = j + c[N + d] - 1;
rollR[y] = max(rollR[y], c[N + d]);
}
}
}
}
for (int j = M - 1; j > 0; j--)
rollR[j - 1] = max(rollR[j - 1], rollR[j] - 1);
for (int j = M; j >= 0; j--) {
int L = i > 0 && j < M ? rollL.at(j) : 0;
int R = j > 0 && i < N ? rollR.at(j - 1) : 0;
/*
if (i > 0 && j < M && rollL.at(j) != dpL.at(i - 1).at(j)) bug(i - 1, j, rollL.at(j), dpL.at(i - 1).at(j));
if (j > 0 && i < N && rollR.at(j - 1) != dpR.at(i).at(j - 1)) bug(i, j - 1, rollR.at(j - 1), dpR.at(i).at(j - 1));
*/
best = max(best, {L + R, i - L, j - R});
}
}
bug(best[0], best[1], best[2]);
return best;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
string S, T;
cin >> S >> T;
auto one = solve(S, T);
reverse(begin(T), end(T));
auto two = solve(S, T);
reverse(begin(T), end(T));
two[2] = sz(T) - two[2] - two[0];
auto best = max(one, two);
cout << best[0] << '\n';
cout << best[1] << ' ' << best[2] << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
250 ms |
540 KB |
Output is correct |
| 2 |
Correct |
247 ms |
344 KB |
Output is correct |
| 3 |
Correct |
256 ms |
348 KB |
Output is correct |
| 4 |
Correct |
214 ms |
528 KB |
Output is correct |
| 5 |
Correct |
236 ms |
536 KB |
Output is correct |
| 6 |
Correct |
263 ms |
596 KB |
Output is correct |
| 7 |
Correct |
251 ms |
348 KB |
Output is correct |
| 8 |
Correct |
234 ms |
540 KB |
Output is correct |
| 9 |
Correct |
243 ms |
344 KB |
Output is correct |
