#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 3030;
int pref[maxn], suf[maxn];
array<int, 3> solve(string s, string t, int rev = 0) {
int n = s.size();
int ans = 0;
int P1 = 0, P2 = 0;
//cout << s << " " << t << endl;
for(int cut = 0; cut < n; cut++) {
memset(pref, 0, sizeof pref);
memset(suf, 0, sizeof suf);
vector<int> b{-1};
for(int i = 0, j = -1; cut+i < n; i++) {
while(j != -1 && s[cut+i] != s[cut+j]) j = b[j];
j++;
b.push_back(j);
}
for(int i = 0, j = 0; i < t.size(); i++) {
while(j != -1 && t[i] != s[cut+j]) j = b[j];
pref[i] = ++j;
if(j+1 == b.size()) j = b.back();
}
if(cut) {
cut--;
vector<int> b{-1};
for(int i = 0, j = -1; cut-i >= 0; i++) {
while(j != -1 && s[cut-i] != s[cut-j]) j = b[j];
j++;
b.push_back(j);
}
for(int i = t.size(), j = 0; i--;) {
while(j != -1 && t[i] != s[cut-j]) j = b[j];
suf[i] = ++j;
if(j+1 == b.size()) j = b.back();
}
cut++;
}
//cout << cut << ":\n";
//for(int i = 0; i < t.size(); i++) cout << pref[i] << " "; cout << endl;
//for(int i = 0; i < t.size(); i++) cout << suf[i] << " "; cout << endl;
for(int i = 0; i < t.size(); i++) {
if(ans < pref[i] + suf[i+1]) {
ans = pref[i]+suf[i+1];
P1 = cut-suf[i+1];
P2 = i+1-pref[i];
if(rev) P2 = t.size()-P2-ans;
//if(ans == 5) cout << cut << " " << i << " " << pref[i] << " " << suf[i+1] << endl;
}
}
}
return {ans, P1, P2};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
string x, y;
cin >> x >> y;
auto ans = solve(x, y);
reverse(all(y));
ans = max(ans, solve(x, y, 1));
cout << ans[0] << '\n' << ans[1] << " " << ans[2] << '\n';
}
Compilation message
necklace.cpp: In function 'std::array<int, 3> solve(std::string, std::string, int)':
necklace.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0, j = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
necklace.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if(j+1 == b.size()) j = b.back();
| ~~~~^~~~~~~~~~~
necklace.cpp:36:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(j+1 == b.size()) j = b.back();
| ~~~~^~~~~~~~~~~
necklace.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
364 KB |
Output is correct |
| 2 |
Correct |
257 ms |
484 KB |
Output is correct |
| 3 |
Correct |
299 ms |
464 KB |
Output is correct |
| 4 |
Correct |
230 ms |
364 KB |
Output is correct |
| 5 |
Correct |
256 ms |
484 KB |
Output is correct |
| 6 |
Correct |
276 ms |
484 KB |
Output is correct |
| 7 |
Correct |
261 ms |
364 KB |
Output is correct |
| 8 |
Correct |
268 ms |
468 KB |
Output is correct |
| 9 |
Correct |
267 ms |
612 KB |
Output is correct |
