#include <bits/stdc++.h>
using namespace std;
char A[3009], B[3009];
int N, M, ans, AI, BI, L[3009][3009], R[3009][3009];
int GL(int i, int j) {
if(i < 1 || j > M) return 0;
if(L[i][j] != -1) return L[i][j];
if(A[i] == B[j]) L[i][j] = 1;
else L[i][j] = 0;
int XX = GL(i-1, j), YY = GL(i, j+1);
if(XX && A[i] == B[j + XX]) L[i][j] = max(L[i][j], XX + 1);
if(YY && A[i - YY] == B[j]) L[i][j] = max(L[i][j], YY + 1);
return L[i][j];
}
int GR(int i, int j) {
if(i > N || j < 1) return 0;
if(R[i][j] != -1) return R[i][j];
if(A[i] == B[j]) R[i][j] = 1;
else R[i][j] = 0;
int XX = GR(i+1, j), YY = GR(i, j-1);
if(XX && A[i] == B[j - XX]) R[i][j] = max(R[i][j], XX + 1);
if(YY && A[i + YY] == B[j]) R[i][j] = max(R[i][j], YY + 1);
return R[i][j];
}
void solve(int x) {
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) L[i][j] = R[i][j] = -1;
for(int i=1; i<N; i++) {
for(int j=1; j<M; j++) {
int vl = (GL(i, j+1) < 0 ? 0 : GL(i, j+1)), vr = (GR(i+1, j) < 0 ? 0 : GR(i+1, j));
int v = vl + vr;
if(ans < v) {
ans = v;
AI = i - vl + 1;
if(x) BI = M - (j + vr);
else BI = j - vr + 1;
}
}
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) {
int v = GL(i, j);
// printf("GL(%d, %d): %d\n", i, j, v);
if(ans < v) {
ans = v;
AI = i - v + 1;
if(x) BI = M - (j + v) + 2;
else BI = j;
}
}
}
}
int main() {
scanf("%s %s", A+1, B+1);
N = strlen(A+1), M = strlen(B+1);
A[0] = A[N+1] = '?'; B[0] = B[M+1] = '!';
solve(0);
reverse(B, B+M+2);
solve(1);
printf("%d\n%d %d", ans, AI - 1, BI - 1);
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s %s", A+1, B+1);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |