// oooo
/*
be hengam shena mesle y dasto pa cholofti ~
bepa to masire dahane koose neyofti ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long long ld;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
const ll inf = 1e18, N = 2e3 + 10, mod = 1e9 + 7, pr = 1000696969;
string s, t;
string st[2][N];
int n, m;
int f[2][N][N * 2];
void calc_f(int x, int y) {
f[x][y][0] = 0;
int k = 0;
for(int i = 1; i < Sz(st[x][y]); i++) {
while(k && st[x][y][k] != st[x][y][i])
k = f[x][y][k - 1];
k += (st[x][y][k] == st[x][y][i]);
f[x][y][i] = k;
}
}
int main() {
fast_io;
cin >>s >>t;
n = Sz(s), m = Sz(t);
st[0][n] = st[1][m] = "";
for(int i = n - 1; i >= 0; i--)
st[0][i] = s[i] + st[0][i + 1];
for(int i = m - 1; i >= 0; i--)
st[1][i] = t[i] + st[1][i + 1];
for(int i = n - 1; i >= 0; i--)
st[0][i] = st[0][i] + '#' + t;
for(int i = m - 1; i >= 0; i--)
st[1][i] = st[1][i] + '#' + s;
for(int i = 0; i < n; i++)
calc_f(0, i);
for(int i = 0; i < m; i++)
calc_f(1, i);
int ans = 0, pos1 = 0, pos2 = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int val = f[1][i][j + m - i + 1];
if(j < n - 1 && i > 0 && n - j + i - 1 < m + n - j)
val += f[0][j + 1][n - j + i - 1];
// if(i == 2 && j == 1)
// cout<<"^^^^" <<val <<endl;
ans = max(ans, val);
if(ans == val) {
pos1 = j - f[1][i][j + m - i + 1] + 1;
pos2 = i - f[0][j + 1][n - j + i - 1];
}
}
}
reverse(all(t));
st[0][n] = st[1][m] = "";
for(int i = n - 1; i >= 0; i--)
st[0][i] = s[i] + st[0][i + 1];
for(int i = m - 1; i >= 0; i--)
st[1][i] = t[i] + st[1][i + 1];
for(int i = n - 1; i >= 0; i--)
st[0][i] = st[0][i] + '#' + t;
for(int i = m - 1; i >= 0; i--)
st[1][i] = st[1][i] + '#' + s;
for(int i = 0; i < n; i++)
calc_f(0, i);
for(int i = 0; i < m; i++)
calc_f(1, i);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int val = f[1][i][j + m - i + 1];
if(j < n - 1 && n - j + i - 1 < m)
val += f[0][j + 1][n - j + i - 1];
ans = max(ans, val);
if(ans == val) {
pos1 = j - f[1][i][j + m - i + 1] + 1;
pos2 = i - f[0][j + 1][n - j + i - 1];
}
}
}
cout<<ans <<endl <<pos1 <<" " <<pos2;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
