#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define ar array
vector<int> kmp(string st)
{
int n = sz(st);
vector<int> f(n);
for (int i = 1; i < n; i++)
{
int j = f[i - 1];
while(j && st[j] != st[i]) j = f[j - 1];
if (st[j] == st[i]) j++;
f[i] = j;
}
return f;
}
string a, b;
ar<int, 3> ans;
/* zxyabcd 7
yxbadctz 8
ztcdabxy
yxz*yxbadctz
abcd*ztcdabxy
*/
void solve(bool isrev)
{
int m = sz(a);
int n = sz(b);
string revb = "";
for (int i = n - 1; i >= 0; i--) revb.push_back(b[i]);
for (int i = 0; i < m; i++)
{
string s1 = a.substr(0, i), s2 = a.substr(i, m - i);
reverse(s1.begin(), s1.end());
vector<int> p1 = kmp(s1 + '*' + b), p2 = kmp(s2 + '*' + revb);
// cout << s1 + '*' + b << ' ' << s2 + '*' + revb << '\n';
for (int j = 1; j <= n; j++)
{
int l1 = i - p1[i + j], l2;
if (!isrev) l2 = j - p1[i + j];
else l2 = n - j - p2[m - i + n - j];
ans = max(ans, {p1[i + j] + p2[m - i + n - j], l1, l2});
// if (i == 3) cout << p1[i + j] + p2[m - i + n - j] << '\n';
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> a >> b;
solve(0);
reverse(b.begin(), b.end());
solve(1);
cout << ans[0] << '\n' << ans[1] << ' ' << ans[2];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
333 ms |
432 KB |
Output is correct |
| 2 |
Correct |
293 ms |
452 KB |
Output is correct |
| 3 |
Correct |
349 ms |
460 KB |
Output is correct |
| 4 |
Correct |
274 ms |
440 KB |
Output is correct |
| 5 |
Correct |
215 ms |
460 KB |
Output is correct |
| 6 |
Correct |
231 ms |
440 KB |
Output is correct |
| 7 |
Correct |
261 ms |
452 KB |
Output is correct |
| 8 |
Correct |
283 ms |
580 KB |
Output is correct |
| 9 |
Correct |
306 ms |
436 KB |
Output is correct |
