#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define pb(a) push_back(a)
#define vll vector<ll>
#define loop(i, n) for (ll i = 1; i <= n; i++)
#define loop0(i, n) for (ll i = 0; i < n; i++)
#define in(i) cin>>i
#define out(i) printf("%lld", i)
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define mp(i, j) make_pair(i, j)
#define google cout << "Case #" << tc - t << ": ";
const ll mod = 1000000007;
const ll big = 2999999999999999999;
const ll small = -2999999999999999999;
void in2(ll &a, ll &b) { cin >> a >> b; }
void in3(ll &a, ll &b, ll &c) {cin >> a >> b >> c; }
void arrayIn(vll &a, ll &n) { loop0(i, n) in(a[i]); }
string s, t;
vll pi1, pi2;
void prefix(string s, vll& pi)
{
ll n = s.size();
pi.resize(n);
pi[0] = 0;
loop(i, n-1)
{
ll j = pi[i-1];
while(j && s[i] != s[j]) j = pi[j-1];
if(s[i] == s[j]) j += 1;
pi[i] = j;
}
}
tuple<ll, ll, ll> solve(string s, string t, bool rev)
{
ll n = s.size();
ll m = t.size();
tuple<ll, ll, ll> ans = {0, 0, 0};
loop0(i, n)
{
string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
reverse(s1.begin(), s1.end());
string t1 = t, t2 = t;
// suffix of s1 that is prefix of t1 for a given j...
reverse(t1.begin(), t1.end());
prefix(s1 + '#' + t1, pi1);
prefix(s2 + '#' + t2, pi2);
loop(j, m)
{
ans = max(ans,
{
pi1[i+j] + pi2[n+m-i-j],
i-pi1[i+j],
!rev ? j - pi2[n+m-i-j] : pi1[i+j]
});
}
}
return ans;
}
void solve()
{
cin >> s >> t;
tuple<ll, ll, ll> ans = solve(s, t, false);
reverse(t.begin(), t.end());
ans = max(solve(s, t, true), ans);
cout<<get<0>(ans)<<"\n"<<get<1>(ans)<<" "<<get<2>(ans)<<"\n";
}
int main()
{
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
302 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
