/** Bismillahir Rahmanir Rahim **/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define endl '\n'
#define fi first
#define se second
#define ull unsigned ll
#define lld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] =>", dbg_out(__VA_ARGS__)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Up, typename... Down> void dbg_out(Up U, Down... D) { cerr << ' ' << U; dbg_out(D...); }
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
string a, b;
int ans = 0, l_idx,l_idx1;
vector<int> kmp(const string &b, const string &a) {
// generating prefix function
int m = sz(b);
vector<int> pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && b[i] != b[j]) j = pi[j - 1];
if (b[i] == b[j]) j++;
pi[i] = j;
}
// genarating chk
int n = sz(a);
vector<int> chk(n, 0);
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && a[i] != b[j]) j = pi[j - 1];
if (a[i] == b[j]) {
j++;
chk[i] = j;
if (j == m) j = pi[j - 1];
}
}
return chk;
}
void solve() {
cin >> a >> b;
string br = b;
reverse(all(br));
// int turn = 2;
int n = sz(a);
int m = sz(b);
// while (turn--) {
// for (int i = 0; i < n; i++) {
// string left = s.substr(0, i);
// reverse(all(left));
// string right = s.substr(i, n - i);
// vector<int> chk = kmp(t, right);
// debug(t, right);
// vector<int> chk1 = kmp(tr, left);
// debug(tr, left);
// reverse(all(chk1));
// int cnt = 0;
// for (int j = 0; j < sz(chk1); j++) {
// if (chk1[j]) {
// cnt++;
// chk1[j] = cnt;
// continue;
// }
// cnt = 0;
// }
// int len = 0;
// for (int j = 0; j < m; j++) {
// int len_right = chk[j];
// int pos = j - len_right;
// int len_left = chk1[pos];
// debug(len_right, pos, len_left);
// if (len_right + len_left > ans) {
// ans = len_right + len_left;
// l_idx = (i - chk1[j]);
// l_idx1 = (j - chk1[j]);
// }
// }
// for (int j = 0; j < m; j++) {
// int len_right = chk1[j];
// int pos = j - len_right;
// int len_left = chk[pos];
// if (len_right + len_left > ans) {
// ans = len_right + len_left;
// l_idx = (i - chk1[j]);
// l_idx1 = (m - (j + 1));
// }
// }
// }
// swap(t, tr);
// }
// cout << ans << endl;
// cout << l_idx << " " << l_idx1 << endl;
int ans = 0, cuta, cutb;
for(int cas = 1; cas <= 2; cas++){
for(int i = 0; i < n; i++){ // reverse before i
string s1 = a.substr(i, n - i), s2 = a.substr(0, i);
vector<int> l, r;
l = kmp(s1, b);
reverse(s2.begin(), s2.end());
r = kmp(s2, br);
reverse(r.begin(), r.end());
if(chkmax(ans, r[0]))
cuta = i - r[0], cutb = (cas == 1 ? 0 : m - r[0]);
if(chkmax(ans, l[m - 1]))
cuta = i, cutb = (cas == 1 ? m - l[m - 1] : 0);
for(int j = 0; j < m - 1; j++)
if(chkmax(ans, l[j] + r[j + 1]))
cuta = i - r[j + 1], cutb = (cas == 1? j - l[j] + 1: m - j - r[j + 1] - 1);
}
swap(b, br);
}
cout << ans << endl;
cout << cuta << " " << cutb << endl;
}
int main()
{
Fastio;
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
Compilation message
necklace.cpp: In function 'void solve()':
necklace.cpp:7:14: warning: 'cutb' may be used uninitialized in this function [-Wmaybe-uninitialized]
7 | #define endl '\n'
| ^~~~
necklace.cpp:119:24: note: 'cutb' was declared here
119 | int ans = 0, cuta, cutb;
| ^~~~
necklace.cpp:143:18: warning: 'cuta' may be used uninitialized in this function [-Wmaybe-uninitialized]
143 | cout << cuta << " " << cutb << endl;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
380 KB |
Output is correct |
| 2 |
Correct |
153 ms |
388 KB |
Output is correct |
| 3 |
Correct |
196 ms |
388 KB |
Output is correct |
| 4 |
Correct |
130 ms |
396 KB |
Output is correct |
| 5 |
Correct |
122 ms |
384 KB |
Output is correct |
| 6 |
Correct |
162 ms |
400 KB |
Output is correct |
| 7 |
Correct |
137 ms |
328 KB |
Output is correct |
| 8 |
Correct |
145 ms |
324 KB |
Output is correct |
| 9 |
Correct |
153 ms |
340 KB |
Output is correct |
