#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 6e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 21;
ll n, m, k;
vector<int>prefix_function(const string& s) {
vector<int>pi = { 0 };
for (int i = 1; i < s.size(); i++) {
int j = pi[i - 1];
while (j > 0 && s[j] != s[i]) {
j = pi[j - 1];
}
if (s[j] == s[i]) {
j++;
}
pi.push_back(j);
}
return pi;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t, rev, cur;
cin >> s >> t;
rev = t;
reverse(rev.begin(), rev.end());
int ans = 0;
int vi = -1, vj = -1;
for (int i = 0; i < s.size(); i++) {
cur = "";
for (int j = 0; j < i; j++) {
cur += s[j];
}
vector<int>pi1(s.size() + t.size() + 1, 0), pi2(s.size() + t.size() + 1, 0);
vector<int>p1, p2;
if (cur != "") {
reverse(cur.begin(), cur.end());
pi1 = prefix_function(cur + '#' + rev);
reverse(pi1.begin() + cur.size() + 1, pi1.end());
for (int j = cur.size() + 1; j < pi1.size(); j++) {
p1.push_back(pi1[j]);
}
}
else {
p1.resize(t.size(), 0);
}
cur = "";
for (int j = i; j < s.size(); j++) {
cur += s[j];
}
if (cur != "") {
pi2 = prefix_function(cur + '#' + t);
for (int j = cur.size() + 1; j < pi2.size(); j++) {
p2.push_back(pi2[j]);
}
}
else {
p2.resize(t.size(), 0);
}
/*cout << i << endl;
for (int x : p1) {
cout << x << " ";
}
cout << endl;
for (int x : p2) {
cout << x << " ";
}
cout << endl;*/
for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
if (ans < p1[j] + p2[j - 1]) {
//cout << i << " " << j << endl;
ans = p1[j] + p2[j - 1];
vi = i - p1[j];
vj = j - p2[j - 1];
}
}
}
reverse(t.begin(), t.end());
reverse(rev.begin(), rev.end());
for (int i = 0; i < s.size(); i++) {
cur = "";
for (int j = 0; j < i; j++) {
cur += s[j];
}
vector<int>pi1(s.size() + t.size() + 1, 0), pi2(s.size() + t.size() + 1, 0);
vector<int>p1, p2;
if (cur != "") {
reverse(cur.begin(), cur.end());
pi1 = prefix_function(cur + '#' + rev);
reverse(pi1.begin() + cur.size() + 1, pi1.end());
for (int j = cur.size() + 1; j < pi1.size(); j++) {
p1.push_back(pi1[j]);
}
}
else {
p1.resize(t.size(), 0);
}
cur = "";
for (int j = i; j < s.size(); j++) {
cur += s[j];
}
if (cur != "") {
pi2 = prefix_function(cur + '#' + t);
for (int j = cur.size() + 1; j < pi2.size(); j++) {
p2.push_back(pi2[j]);
}
}
else {
p2.resize(t.size(), 0);
}
/*cout << i << endl;
for (int x : p1) {
cout << x << " ";
}
cout << endl;
for (int x : p2) {
cout << x << " ";
}
cout << endl;*/
for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
if (ans < p1[j] + p2[j - 1]) {
//cout << i << " " << j << endl;
ans = p1[j] + p2[j - 1];
vi = i - p1[j];
vj = j - p2[j - 1];
vj = t.size() - ans - vj;
}
}
}
cout << ans << endl;
cout << vi << " " << vj << endl;
return 0;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
Compilation message
necklace.cpp: In function 'std::vector<int> prefix_function(const string&)':
necklace.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 1; i < s.size(); i++) {
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
necklace.cpp:72:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = cur.size() + 1; j < pi1.size(); j++) {
| ~~^~~~~~~~~~~~
necklace.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int j = i; j < s.size(); j++) {
| ~~^~~~~~~~~~
necklace.cpp:85:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int j = cur.size() + 1; j < pi2.size(); j++) {
| ~~^~~~~~~~~~~~
necklace.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
| ~~^~~~~~~~~~~
necklace.cpp:101:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
| ~~~~~~^~~~~~~~~~~
necklace.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
necklace.cpp:123:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int j = cur.size() + 1; j < pi1.size(); j++) {
| ~~^~~~~~~~~~~~
necklace.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int j = i; j < s.size(); j++) {
| ~~^~~~~~~~~~
necklace.cpp:136:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int j = cur.size() + 1; j < pi2.size(); j++) {
| ~~^~~~~~~~~~~~
necklace.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
| ~~^~~~~~~~~~~
necklace.cpp:152:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
624 ms |
612 KB |
Output is correct |
| 2 |
Correct |
591 ms |
588 KB |
Output is correct |
| 3 |
Correct |
665 ms |
620 KB |
Output is correct |
| 4 |
Correct |
552 ms |
468 KB |
Output is correct |
| 5 |
Correct |
497 ms |
468 KB |
Output is correct |
| 6 |
Correct |
541 ms |
844 KB |
Output is correct |
| 7 |
Correct |
582 ms |
476 KB |
Output is correct |
| 8 |
Correct |
588 ms |
468 KB |
Output is correct |
| 9 |
Correct |
603 ms |
588 KB |
Output is correct |
