#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int p1 = 1e4 + 7;
const int p2 = 1e9 + 9;
string s, t;
int prefs[3010], preft[3010];
int h(string const& s) {
int r = 0;
int p = 1;
for(int i = 0; i < s.size(); i++) {
r += (p * (s[i] - 'a' + 1))%p2;
r %= p2;
p *= p1;
p %= p2;
}
return r;
}
int power(int a, int b) {
int r = 1;
a %= p2;
while(b) {
if(b&1) r *= a, r %= p2;
a *= a;
a %= p2;
b >>= 1;
}
return r;
}
int h_s(int a, int t) {
int b = t + a - 1;
return ((((prefs[b] - (a == 0 ? 0 : prefs[a-1])) * power(p1, a*(p2-2)))%p2)+p2)%p2;
}
int h_t(int a, int t) {
int b = t + a - 1;
return ((((preft[b] - (a == 0 ? 0 : preft[a-1])) * power(p1, a*(p2-2)))%p2)+p2)%p2;
}
bool mark[3010][3010];
mt19937 gen(random_device{}());
int maximo=1, ini, fim;
void solve(bool rev) {
memset(mark, 0, sizeof mark);
uniform_int_distribution<> ri(0, s.size()-1);
uniform_int_distribution<> rj(0, t.size()-1);
int porta = (max(s.size(), t.size())*max(s.size(), t.size()))/maximo;
for(int c=1; c <= porta; c++) {
int i = ri(gen), j = rj(gen);
int b_a=0, b_b=0;
// if(mark[i][j]) {
// c--;
// continue;
// }
// while(i - a >= 0 && j + a <= t.size() && i + b <= s.size() && j - b >= 0 &&
// s[i - a] == t[j + a - 1] && s[i + b - 1] == t[])
for(int a = maximo/2; i - a >= 0 && j + a <= t.size(); a++) {
if(h_s(i-a, a) == h_t(j, a))
b_a = a;
}
if(b_a == 0){
for(int b = maximo/2; i + b <= s.size() && j - b >= 0; b++) {
if(h_s(i, b) == h_t(j - b, b)){
b_b = b;
}
}
if(b_b == 0) continue;
for(int a = maximo - b_b; i - a >= 0 && j + a <= t.size(); a++) {
if(h_s(i-a, a) == h_t(j, a))
b_a = a;
}
if(b_a == 0) continue;
}else{
for(int b = maximo - b_a; i + b <= s.size() && j - b >= 0; b++) {
if(h_s(i, b) == h_t(j - b, b)){
b_b = b;
}
}
}
if(b_b == 0)
continue;
// if(b_a != 0 && b_b != 0) cout << b_a << " " << b_b << ": " << b_a + b_b << "\n";
if(b_a + b_b > maximo) {
maximo = b_a + b_b;
ini = i - b_a;
if(rev) fim = t.size() - (j + b_a);
else fim = j - b_b;
porta = (max(s.size(), t.size())*max(s.size(), t.size()))/maximo;
}
}
}
int32_t main() {
cin >> s >> t;
// cout << "\n" << s << "\n";
// cout << t << "\n";
// cout << h(s) << " " << h(t) << "\n";
int p = 1;
for(int i = 0; i < s.size(); i++) {
prefs[i] = ((i==0?0:prefs[i-1]) + ( p * (s[i] - 'a' + 1) )%p2) % p2;
p *= p1;
p %= p2;
}
p = 1;
for(int i = 0; i < t.size(); i++) {
preft[i] = ((i==0?0:preft[i-1]) + ( p * (t[i] - 'a' + 1) )%p2) % p2;
p *= p1;
p %= p2;
}
// for(int i = 0; i < 5; i++) {
// for(int j = i; j < 5; j++) {
// cout << i << " " << j << ": " << h(s.substr(i, j-i+1)) << " " << h_s(i, j-i+1) << "\n";
// }
// }
// cout << h("hia") << " " << h_s(1, 3) << "D\n";
solve(false);
reverse(t.begin(), t.end());
// memset(preft, 0, sizeof preft);
p = 1;
for(int i = 0; i < t.size(); i++) {
preft[i] = ((i==0?0:preft[i-1]) + ( p * (t[i] - 'a' + 1) )%p2) % p2;
p *= p1;
p %= p2;
}
solve(true);
cout << maximo << "\n" << ini << " " << fim << "\n";
return 0;
}
Compilation message
necklace.cpp: In function 'int64_t h(const string&)':
necklace.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++) {
~~^~~~~~~~~~
necklace.cpp: In function 'void solve(bool)':
necklace.cpp:68:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = maximo/2; i - a >= 0 && j + a <= t.size(); a++) {
~~~~~~^~~~~~~~~~~
necklace.cpp:73:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b = maximo/2; i + b <= s.size() && j - b >= 0; b++) {
~~~~~~^~~~~~~~~~~
necklace.cpp:79:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = maximo - b_b; i - a >= 0 && j + a <= t.size(); a++) {
~~~~~~^~~~~~~~~~~
necklace.cpp:86:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b = maximo - b_a; i + b <= s.size() && j - b >= 0; b++) {
~~~~~~^~~~~~~~~~~
necklace.cpp: In function 'int32_t main()':
necklace.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < t.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < t.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
15 ms |
9212 KB |
Output is partially correct |
| 2 |
Partially correct |
13 ms |
9228 KB |
Output is partially correct |
| 3 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 4 |
Partially correct |
30 ms |
9208 KB |
Output is partially correct |
| 5 |
Partially correct |
138 ms |
9336 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
15 ms |
9212 KB |
Output is partially correct |
| 2 |
Partially correct |
13 ms |
9228 KB |
Output is partially correct |
| 3 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 4 |
Partially correct |
30 ms |
9208 KB |
Output is partially correct |
| 5 |
Partially correct |
138 ms |
9336 KB |
Output is partially correct |
| 6 |
Partially correct |
35 ms |
9208 KB |
Output is partially correct |
| 7 |
Partially correct |
47 ms |
9284 KB |
Output is partially correct |
| 8 |
Partially correct |
295 ms |
9208 KB |
Output is partially correct |
| 9 |
Partially correct |
269 ms |
9252 KB |
Output is partially correct |
| 10 |
Partially correct |
1408 ms |
9208 KB |
Output is partially correct |
| 11 |
Execution timed out |
1570 ms |
9208 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
15 ms |
9212 KB |
Output is partially correct |
| 2 |
Partially correct |
13 ms |
9228 KB |
Output is partially correct |
| 3 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 4 |
Partially correct |
30 ms |
9208 KB |
Output is partially correct |
| 5 |
Partially correct |
138 ms |
9336 KB |
Output is partially correct |
| 6 |
Partially correct |
35 ms |
9208 KB |
Output is partially correct |
| 7 |
Partially correct |
47 ms |
9284 KB |
Output is partially correct |
| 8 |
Partially correct |
295 ms |
9208 KB |
Output is partially correct |
| 9 |
Partially correct |
269 ms |
9252 KB |
Output is partially correct |
| 10 |
Partially correct |
1408 ms |
9208 KB |
Output is partially correct |
| 11 |
Execution timed out |
1570 ms |
9208 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
