/** 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...); }
string s, t;
int ans = 0, l_idx,l_idx1;
vector<int> kmp(const string &a, const string &b) {
// 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 >> s >> t;
string tr = t;
reverse(all(tr));
int turn = 2;
int n = sz(s);
int m = sz(t);
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 main()
{
Fastio;
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
Compilation message
necklace.cpp: In function 'void solve()':
necklace.cpp:84:17: warning: unused variable 'len' [-Wunused-variable]
84 | int len = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1558 ms |
5980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
