#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 PA[N + 1][26], PB[N+1][26];
int n,m;
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);
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s >> t;
n = s.size();
m = t.size();
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]++;
}
}
int ans = 0;
pair<int, int> start = {-1, -1};
for(int len = 1; len <= min(n, m); len++){
string A = "";
for(int idx = 0; idx < len; idx++) A+= s[idx];
for(int i = 0;i + len-1 < n && ans < len; i++){
string B = "";
for(int idx = 0; idx < len; idx++) B+= t[idx];
for(int j = 0;j + len-1 < m && ans < len; j++){
if(good(A, B)){
ans = len;
start = {i, j};
break;
}
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());
}
}
cout << ans << '\n';
cout << start.ff << ' ' << start.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: In function 'int getA(int, int, char)':
necklace.cpp:46:15: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);
| ^~
necklace.cpp:46:36: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);
| ^~
necklace.cpp: At global scope:
necklace.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
348 KB |
Output is correct |
| 2 |
Correct |
48 ms |
600 KB |
Output is correct |
| 3 |
Correct |
109 ms |
344 KB |
Output is correct |
| 4 |
Correct |
154 ms |
468 KB |
Output is correct |
| 5 |
Correct |
245 ms |
472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
348 KB |
Output is correct |
| 2 |
Correct |
48 ms |
600 KB |
Output is correct |
| 3 |
Correct |
109 ms |
344 KB |
Output is correct |
| 4 |
Correct |
154 ms |
468 KB |
Output is correct |
| 5 |
Correct |
245 ms |
472 KB |
Output is correct |
| 6 |
Execution timed out |
1543 ms |
1040 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
348 KB |
Output is correct |
| 2 |
Correct |
48 ms |
600 KB |
Output is correct |
| 3 |
Correct |
109 ms |
344 KB |
Output is correct |
| 4 |
Correct |
154 ms |
468 KB |
Output is correct |
| 5 |
Correct |
245 ms |
472 KB |
Output is correct |
| 6 |
Execution timed out |
1543 ms |
1040 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
