#include<bits/stdc++.h>
//#include"tickets.h"
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf = 1e9;
using namespace std;
string s;
string s2;
string s3;
ll compare(ll start, ll end) {
bool ans = false;
ll res = -1;
rep(i, 0, s.size() - (end - start) + 1) {
rep(j, 0, end-start) {
bool done = true;
rep(z, 0, end - start) {
if (s2[start+((j+z) % (end - start))] != s[i + z]) {
done = false;
break;
}
}
if (done) {
ans = true;
res = i;
break;
}
}
if (ans)break;
rep(j, 0, end - start) {
bool done = true;
rep(z, 0, end - start) {
if (s3[(start)+((j+z) % (end - start))] != s[i + z]) {
done = false;
break;
}
}
if (done) {
ans = true;
res = i;
break;
}
}
if (ans)break;
}
return res;
}
int main() {
cin.sync_with_stdio(false);
cin >> s >> s2;
s3 = s2;
reverse(all(s3));
cout << compare(2, 6);
ll cur = 0;
pair<ll, pair<ll, ll>> res = make_pair(-inf, make_pair(-inf, -inf));
while (cur <= s.size()) {
ll l = 1, r = s.size();
pair<ll, ll> best = make_pair(0, 0);
while (l <= r) {
ll mid = l + (r - l) / 2;
ll val = compare(cur, mid);
if (compare(cur, mid) != -1) {
best = make_pair(mid - cur, val);
l = mid + 1;
}
else r = mid - 1;
}
if (res.first < best.first) {
res.first = best.first;
res.second.first = cur;
res.second.second = best.second;
}
cur += best.first + 1;
}
cout << res.first << endl;
cout << res.second.first << " " << res.second.second << endl;
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:66:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while (cur <= s.size()) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
