#include <bits/stdc++.h>
using namespace std;
vector<int> prefix_function(string const& s) {
int n = size(s);
vector<int> pi(n);
for (int i = 1; i < size(s); i++) {
int j = pi[i-1];
while (j && s[i] != s[j]) j = pi[j-1];
while (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
array<int, 3> solve(string const& s, string const& t, bool rev) {
int n = size(s), m = size(t);
array<int, 3> ans{0, 0, 0};
string tr = t;
reverse(begin(tr), end(tr));
for (int i = 0; i < n; i++) {
string s1 = s.substr(0, i), s2 = s.substr(i, n-(i+1));
auto p1 = prefix_function(s2 + '$' + t);
reverse(begin(s1), end(s1));
auto p2 = prefix_function(s1 + '$' + tr);
/* cout << s2 << '$' << t << endl; */
/* for (auto x : p1) cout << x; */
/* cout << endl; */
/**/
/* cout << s1 << '$' << tr << endl; */
/* for (auto x : p2) cout << x; */
/* cout << endl; */
for (int j = 0; j < m; j++) {
int blen = p1[size(s2)+1+j];
int alen = p2[size(p2)-1-j-1];
if (alen + blen > ans[0]) {
ans[0] = alen + blen;
ans[1] = i - alen + 1;
ans[2] = j - blen + 1;
if (!rev) ans[2] = m - 1 - j;
}
}
}
return ans;
}
int main() {
string s, t;
cin >> s >> t;
auto ans = solve(s, t, false);
reverse(begin(t), end(t));
ans = max(ans, solve(s, t, true));
cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << endl;
}
Compilation message
necklace.cpp: In function 'std::vector<int> prefix_function(const string&)':
necklace.cpp:8:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for (int i = 1; i < size(s); i++) {
| ~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1572 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
