#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < n; i++)
#define w(t) \
int t; \
cin >> t; \
while (t--)
#define ff first
#define ss second
#define in(azz, sz) \
for (int ix = 0; ix < sz; ix++) \
cin >> azz[ix];
#define in2d(azz, row, column) rep(i, row) rep(j, column) cin >> azz[i][j];
#define out2d(azz, row, column) \
rep(i, row) \
{ \
rep(j, column) cout << azz[i][j] << " "; \
cout << "\n" \
};
#define out(azz, sz) \
for (int ix = 0; ix < sz; ix++) \
{ \
cout << azz[ix] << " "; \
} \
cout << endl
#define mii map<int, int>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define endl '\n'
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ps(x, y) fixed << setprecision(y) << x
#define mp make_pair
#define all(vx) vx.begin(), vx.end()
#define maxv(azz) max_element(all(azz)) - azz.begin() //return index of max element of vector;
#define minv(azz) min_element(all(azz)) - azz.begin() //return index of min element of vector;
#define maxa(azz) max_element(azz, azz + n) - azz //return index of max element of array, n==size of array;
#define mina(azz) min_element(azz, azz + n) - azz //return index of min element of array, n==size of array;
#define isort(azz) is_sorted(all(azz)) //check if elements are sorted;
#define setpres cout.precision(numeric_limits<double>::max_digits10);
#define rev(vx) reverse(all(vx))
#define fastio \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> seti;
#define am(a, b) MOD(MOD(a) + MOD(b))
#define mm(a, b) MOD(MOD(a) * MOD(b))
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const ll INF = 1000000007;
ll MOD(ll a)
{
a = a % INF;
while (a < 0)
a += INF;
return a;
}
ll binpow(ll a, ll b)
{
ll res = 1;
while (b > 0)
{
if (b & 1)
res = mm(res, a);
a = mm(a, a);
b >>= 1;
}
return res;
}
ll modInverse(ll a)
{
return binpow(a, INF - 2);
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DON'T MAKE CHANGES BEFORE THIS LINE!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#define int ll //use only if needed;
vector<int> prefix_function(string s)
{
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
{
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
/*
$A$ is a suffix of $S[0 : i]$ and a prefix of $T[j + 1 : M - 1]$.
$B$ is a prefix of $S[i + 1 : N - 1]$ and a suffix of $T[0 : j]$.
$|A| + |B|$ is maximal.
*/
void tosolve()
{
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size(), ans = 0, l, r;
rep(i, n)
{
string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
reverse(s1.begin(), s1.end());
string t1 = t, t2 = t;
reverse(t2.begin(), t2.end());
vi temp1 = prefix_function(s1 + "#" + t1);
vi temp2 = prefix_function(s2 + "#" + t2);
for (int j = 0; j < m; j++)
{
if (ans <= temp1[i + j] + temp2[n + m - i - j])
{
ans = max(ans, temp1[i + j] + temp2[n + m - i - j]);
l = i - temp1[i + j];
r = j - temp1[i + j];
}
}
}
reverse(t.begin(), t.end());
rep(i, n)
{
string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
reverse(s1.begin(), s1.end());
string t1 = t, t2 = t;
reverse(t2.begin(), t2.end());
vi temp1 = prefix_function(s1 + "#" + t1);
vi temp2 = prefix_function(s2 + "#" + t2);
for (int j = 0; j < m; j++)
{
if (ans <= temp1[i + j] + temp2[n + m - i - j])
{
ans = max(ans, temp1[i + j] + temp2[n + m - i - j]);
l = i - temp1[i + j];
r = m - j - temp2[n + m - i - j];
}
}
}
cout << ans << endl;
cout << l << " " << r << endl;
return;
}
int32_t main()
{
fastio
{
tosolve();
}
return 0;
}
/*
███╗░░░███╗██╗████████╗██╗░░██╗██╗██╗░░░░░
████╗░████║██║╚══██╔══╝██║░░██║██║██║░░░░░
██╔████╔██║██║░░░██║░░░███████║██║██║░░░░░
██║╚██╔╝██║██║░░░██║░░░██╔══██║██║██║░░░░░
██║░╚═╝░██║██║░░░██║░░░██║░░██║██║███████╗
╚═╝░░░░░╚═╝╚═╝░░░╚═╝░░░╚═╝░░╚═╝╚═╝╚══════╝
* Author : mithilshah23
* Website : Oj
* Problem : necklace
* Time : 17-08-2021 20:49:52
* Lang : GNU C++17
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
313 ms |
468 KB |
Output is correct |
| 2 |
Correct |
282 ms |
588 KB |
Output is correct |
| 3 |
Correct |
330 ms |
476 KB |
Output is correct |
| 4 |
Correct |
260 ms |
464 KB |
Output is correct |
| 5 |
Correct |
232 ms |
460 KB |
Output is correct |
| 6 |
Correct |
254 ms |
468 KB |
Output is correct |
| 7 |
Correct |
264 ms |
572 KB |
Output is correct |
| 8 |
Correct |
287 ms |
452 KB |
Output is correct |
| 9 |
Correct |
300 ms |
480 KB |
Output is correct |
