#include "bits/stdc++.h"
using namespace std;
signed main () {
string a, b;
function <int(queue <char>)> get=[&](queue <char> str) {
queue <char> ttr;
int k = str.size();
set <queue <char>> shift;
int cnt = str.size();
while(cnt --) {
shift.insert(str);
str.push(str.front());
str.pop();
}
for(int i = 0; i < k; i ++) ttr.push(b[i]);
for(int i = k; i < b.size(); i ++) {
if(shift.count(ttr)) {
return i-k;
}
ttr.pop();
ttr.push(b[i]);
}
if(shift.count(ttr)) {
return (int)b.size()-k;
}
return -1;
};
cin >> a >> b;
if(a.size() <= 100 && b.size() <= 100) {
int mx = -1, grana, granb;
for(int l = 0; l < a.size(); l ++) {
queue <char> str;
for(int r = l; r < a.size(); r ++) {
str.push(a[r]);
int temp = get(str);
if(temp == -1) continue;
// cout << l << " " <</ r << " " << temp << "\n";
if(temp != -1) {
if(r-l+1 > mx) {
mx = r-l+1;
grana = l;
granb = temp;
}
}
}
}
reverse(b.begin(), b.end());
for(int l = 0; l < a.size(); l ++) {
queue <char> str;
for(int r = l; r < a.size(); r ++) {
str.push(a[r]);
int temp = get(str);
if(temp == -1) continue;
// cout << l << " " << r << " " << temp << "\n";
if(temp != -1) {
if(r-l+1 > mx) {
mx = r-l+1;
granb = b.size() - (temp+(r-l+1));
grana = l;
}
}
}
}
cout << mx << "\n" << grana << " " << granb;
return 0;
}
function<pair <int,int>(int)> good=[&](int sz) {
if(sz == 0) return make_pair(1,1);
queue <char> str;
if(sz > a.size()) return make_pair(-1,-1);
for(int i = 0; i < sz; i ++) str.push(a[i]);
for(int i = sz; i < a.size(); i ++) {
if(get(str) != -1) {
return make_pair(i - sz, get(str));
}
str.pop();
str.push(a[i]);
}
if(get(str) != -1) return make_pair((int)a.size() - sz, get(str));
return make_pair(-1,-1);
};
// for(int i = 0; i < min(a.size(), b.size()); i ++) {
// cout << good(i).first << " " << good(i).second << "\n";
// }
int l = 0, r = min(a.size(), b.size());
while(l < r) {
int mid = (l + r + 1) / 2;
if(good(mid).first != -1) l = mid;
else r = mid-1;
}
// cout << l << " ";
int mx = l, grana = good(l).first, granb = good(l).second;
if(good(l).first == -1) {
mx = 0;
grana = granb = 0;
}
reverse(b.begin(), b.end());
l = 1, r = min(a.size(), b.size());
while(l < r) {
int mid = (l + r + 1) / 2;
if(good(mid).first != -1) l = mid;
else r = mid-1;
}
if(l > mx && good(l).first != -1) {
mx = l;
grana = good(l).first;
granb = b.size() - (good(l).second+mx);
}
cout << mx << "\n" << grana << " " << granb;
return 0;
}
Compilation message
necklace.cpp: In lambda function:
necklace.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = k; i < b.size(); i ++) {
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int l = 0; l < a.size(); l ++) {
| ~~^~~~~~~~~~
necklace.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int r = l; r < a.size(); r ++) {
| ~~^~~~~~~~~~
necklace.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int l = 0; l < a.size(); l ++) {
| ~~^~~~~~~~~~
necklace.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int r = l; r < a.size(); r ++) {
| ~~^~~~~~~~~~
necklace.cpp: In lambda function:
necklace.cpp:72:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(sz > a.size()) return make_pair(-1,-1);
| ~~~^~~~~~~~~~
necklace.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = sz; i < a.size(); i ++) {
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:66:41: warning: 'granb' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | cout << mx << "\n" << grana << " " << granb;
| ^~~~~
necklace.cpp:66:34: warning: 'grana' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | cout << mx << "\n" << grana << " " << granb;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
348 KB |
Output is correct |
| 2 |
Correct |
127 ms |
348 KB |
Output is correct |
| 3 |
Correct |
76 ms |
468 KB |
Output is correct |
| 4 |
Correct |
111 ms |
348 KB |
Output is correct |
| 5 |
Correct |
90 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
348 KB |
Output is correct |
| 2 |
Correct |
127 ms |
348 KB |
Output is correct |
| 3 |
Correct |
76 ms |
468 KB |
Output is correct |
| 4 |
Correct |
111 ms |
348 KB |
Output is correct |
| 5 |
Correct |
90 ms |
348 KB |
Output is correct |
| 6 |
Correct |
439 ms |
664 KB |
Output is correct |
| 7 |
Partially correct |
667 ms |
604 KB |
Output is partially correct |
| 8 |
Correct |
568 ms |
348 KB |
Output is correct |
| 9 |
Partially correct |
365 ms |
596 KB |
Output is partially correct |
| 10 |
Partially correct |
256 ms |
348 KB |
Output is partially correct |
| 11 |
Partially correct |
226 ms |
344 KB |
Output is partially correct |
| 12 |
Correct |
642 ms |
544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
348 KB |
Output is correct |
| 2 |
Correct |
127 ms |
348 KB |
Output is correct |
| 3 |
Correct |
76 ms |
468 KB |
Output is correct |
| 4 |
Correct |
111 ms |
348 KB |
Output is correct |
| 5 |
Correct |
90 ms |
348 KB |
Output is correct |
| 6 |
Correct |
439 ms |
664 KB |
Output is correct |
| 7 |
Partially correct |
667 ms |
604 KB |
Output is partially correct |
| 8 |
Correct |
568 ms |
348 KB |
Output is correct |
| 9 |
Partially correct |
365 ms |
596 KB |
Output is partially correct |
| 10 |
Partially correct |
256 ms |
348 KB |
Output is partially correct |
| 11 |
Partially correct |
226 ms |
344 KB |
Output is partially correct |
| 12 |
Correct |
642 ms |
544 KB |
Output is correct |
| 13 |
Execution timed out |
1541 ms |
2904 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
