#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 401;
vector<int> z_function(string s){
int n =(int)s.size();
vector<int> z(n);
for(int i=1, l=0, r=0; i<n; ++i){
if(i <= r)
z[i] = min (r-i+1, z[i-l]);
while(i+z[i] < n && s[z[i]] == s[i+z[i]])
++z[i];
if(i+z[i]-1 > r)
l = i, r = i+z[i]-1;
}
return z;
}
int has_sub(string a, string b){
vector<int> z = z_function(b + "#" + a);
for(int i = b.size() + 1; i < z.size(); i++){
if(z[i] == b.size()) return 1;
}
return 0;
}
int good(string a, string b){
if(has_sub(a + a, b)) return 1;
reverse(all(b));
if(has_sub(a + a, b)) return 1;
return 0;
}
string s, t;
int n,m;
pair<int, int> start;
int check(int len){
if(len > min(n, m)) return 0;
if(len== 0) return 1;
string A = "";
for(int idx = 0; idx < len; idx++) A+= s[idx];
for(int i = 0;i + len-1 < n; i++){
string B = "";
for(int idx = 0; idx < len; idx++) B+= t[idx];
for(int j = 0;j + len-1 < m; j++){
if(good(A, B)){
start = {i, j};
return 1;
}
B.erase(B.begin());
if(j + len < m) B.push_back(t[j + len]);
}
if(i + len < n)A.push_back(s[i + len]);
A.erase(A.begin());
}
return 0;
}
/*
int PA[N + 1][26], PB[N+1][26];
int getA(int l, int r, char ch){
return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);
}
int getB(int l, int r, int ch){
return PB[r][ch]-(l > 0 ? PB[l-1][ch] : 0);
}
for(int i = 0;i < n; i++){
for(int j = 0;j < 26; j++){
PA[i][j] = (i > 0 ? PA[i-1][j] : 0);
if(s[i]-'a' == j) PA[i][j]++;
}
}
for(int i = 0;i < m; i++){
for(int j = 0;j < 26; j++){
PB[i][j] = (i > 0 ? PB[i-1][j] : 0);
if(t[i]-'a' == j) PB[i][j]++;
}
}*/
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s >> t;
n = s.size();
m = t.size();
int l = 0, r = min(n, m) + 1;
pair<int, int> ANS = {-1, -1};
while(l + 1 < r){
int mid = (l + r) >> 1;
start = {-1, -1};
if(check(mid)){
l = mid;
ANS = start;
}else r = mid;
}
// if(l == 0) assert(false);
cout << l << '\n';
if(ANS.ff == -1) assert(false);
cout << ANS.ff << ' ' << ANS.ss;
return 0;
}
Compilation message
necklace.cpp: In function 'int has_sub(std::string, std::string)':
necklace.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i = b.size() + 1; i < z.size(); i++){
| ~~^~~~~~~~~~
necklace.cpp:26:11: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if(z[i] == b.size()) return 1;
necklace.cpp: At global scope:
necklace.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
348 KB |
Output is correct |
| 2 |
Partially correct |
3 ms |
464 KB |
Output is partially correct |
| 3 |
Correct |
14 ms |
348 KB |
Output is correct |
| 4 |
Partially correct |
19 ms |
348 KB |
Output is partially correct |
| 5 |
Correct |
21 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
348 KB |
Output is correct |
| 2 |
Partially correct |
3 ms |
464 KB |
Output is partially correct |
| 3 |
Correct |
14 ms |
348 KB |
Output is correct |
| 4 |
Partially correct |
19 ms |
348 KB |
Output is partially correct |
| 5 |
Correct |
21 ms |
604 KB |
Output is correct |
| 6 |
Correct |
77 ms |
456 KB |
Output is correct |
| 7 |
Partially correct |
270 ms |
344 KB |
Output is partially correct |
| 8 |
Execution timed out |
1533 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
348 KB |
Output is correct |
| 2 |
Partially correct |
3 ms |
464 KB |
Output is partially correct |
| 3 |
Correct |
14 ms |
348 KB |
Output is correct |
| 4 |
Partially correct |
19 ms |
348 KB |
Output is partially correct |
| 5 |
Correct |
21 ms |
604 KB |
Output is correct |
| 6 |
Correct |
77 ms |
456 KB |
Output is correct |
| 7 |
Partially correct |
270 ms |
344 KB |
Output is partially correct |
| 8 |
Execution timed out |
1533 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
