#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
int N, M, pa[3009][3009]; long long as[3009], at[3009], power[3009];
int EA[6009], EB[6009];
int get_pb(int l, int r) {
int len = 0;
for (int i = 11; i >= 0; i--) {
int cx = len + (1 << i);
if (!(l + cx - 1 < N && r + cx - 1 < M)) continue;
long long v1 = as[r + 1] - as[l] * power[r - l + 1];
long long v2 = at[r + 1] - at[l] * power[r - l + 1];
if (v1 == v2) len = cx;
}
return len;
}
tuple<int, int, int> solve(string S, string T) {
for (int i = 0; i <= 3000; i++) { as[i] = 0; at[i] = 0; power[i] = 0; }
for (int i = 0; i < S.size(); i++) {
as[i + 1] = as[i] * 101LL;
as[i + 1] += (S[i] - 'a' + 1);
}
for (int i = 0; i < T.size(); i++) {
at[i + 1] += at[i] * 101LL;
at[i + 1] += (T[i] - 'a' + 1);
}
power[0] = 1; for (int i = 1; i <= 3000; i++) power[i] = (101LL * power[i - 1]);
N = S.size(); M = T.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
pa[i][j] = 0;
if (S[i] == T[j]) pa[i][j] = 1;
if (i >= 1 && j >= 1 && S[i] == T[j]) {
pa[i][j] = pa[i - 1][j - 1] + 1;
}
}
}
int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
for (int i = 0; i <= N; i++) {
// S における境界が i の場合
vector<int> A, B;
for (int j = 0; j < M; j++) {
if (i == N) A.push_back(0);
else A.push_back(get_pb(i, j));
}
for (int j = 0; j < M; j++) {
if (i == 0) B.push_back(0);
else B.push_back(pa[i - 1][j]);
}
for (int j = 0; j <= 6000; j++) { EA[j] = (1 << 29); EB[j] = -(1 << 29); }
for (int j = 0; j < N; j++) {
EA[A[j] + j] = min(EA[A[j] + j], j);
EB[max(0, -B[j] + j + 1)] = max(EB[max(0, -B[j] + j + 1)], j);
}
// ret1 には条件を満たす最も左のインデックスを記録
int ret1 = -(1 << 29);
for (int j = 0; j <= 6000; j++) {
ret1 = max(ret1, EB[j]);
int cr = ret1, cl = EA[j];
if (maxn < cr - cl + 1) {
maxn = cr - cl + 1;
maxid = make_pair(i - B[cr], cl);
}
}
}
return make_tuple(maxn, maxid.first, maxid.second);
}
int main() {
string A1, B1, B2; cin >> A1 >> B1; B2 = B1; reverse(B2.begin(), B2.end());
tuple<int, int, int> v1 = solve(A1, B1);
tuple<int, int, int> v2 = solve(A1, B2);
cout << max(get<0>(v1), get<0>(v2)) << endl;
if (get<0>(v1) > get<0>(v2)) cout << get<1>(v1) << " " << get<2>(v1) << endl;
if (get<0>(v1) <= get<0>(v2)) cout << get<1>(v2) << " " << M - (get<2>(v2) + get<0>(v2)) << endl;
return 0;
}
Compilation message
necklace.cpp: In function 'std::tuple<int, int, int> solve(std::__cxx11::string, std::__cxx11::string)':
necklace.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
