#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 3005;
int kmp[N];
int fw[N];
int bw[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string S; cin >> S;
string T; cin >> T;
int n = sz(S);
int m = sz(T);
auto build = [&](int *f) {
kmp[0] = -1;
for(int i = 1 ; i <= m ; ++i) kmp[i] = 0;
for(int i = 1 ; i <= n ; ++i) f[i] = 0;
for(int i = 2 ; i <= m ; ++i)
for(int j = kmp[i - 1] ; j >= 0 ; j = kmp[j])
if (T[i - 1] == T[j]) {
kmp[i] = j + 1;
break;
}
for(int i = 1 ; i <= n ; ++i)
for(int j = f[i - 1] ; j >= 0 ; j = kmp[j])
if (S[i - 1] == T[j]) {
f[i] = j + 1;
break;
}
};
auto Solve = [&]() {
array<int,3> ans = {0,0,0};
for(int i = 1 ; i <= m ; ++i) {
build(fw);
reverse(all(S));
reverse(all(T));
build(bw);
reverse(all(S));
reverse(all(T));
reverse(bw + 1,bw + 1 + n);
for(int j = 1 ; j <= n ; ++j) {
int len1 = min(fw[j],m - i + 1);
int len2 = min(bw[j + 1],i - 1);
if (ans[0] < len1 + len2) {
ans[0] = len1 + len2;
ans[1] = j - len1;
ans[2] = i - len2 - 1;
}
}
T = T.back() + T;
T.pop_back();
}
return ans;
};
auto ans1 = Solve(); reverse(all(T));
auto ans2 = Solve();
if (ans1[0] > ans2[0]) cout << ans1[0] << "\n" << ans1[1] << " " << ans1[2];
else cout << ans2[0] << "\n" << ans2[1] << " " << ans2[2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
