#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define mod 1000000007
#define prim 29
#define MAX 3000
struct str{
lli val;
lli a;
lli b;
};
string st[3];
lli acu[3][MAX+2],tam[3], divi[MAX+4], pot[MAX+4];
lli n,m,k,sss;
str x,res;
void inverso() {
lli res = 1;
lli pot = prim;
lli num = mod-2;
while (num > 0) {
if (num&1) {
res *= pot;
res %= mod;
}
num/=2;
pot *= pot;
pot %= mod;
}
divi[0] = 1;
divi[1] = res;
rep(i,2,max(tam[0],tam[1])) {divi[i] = divi[i-1]*res; divi[i]%=mod;}
}
lli query(lli ini, lli fin, lli ind) {
lli res = acu[ind][fin];
if (ini > 0) res -= acu[ind][ini-1];
if (res < 0) res += mod;
res *= divi[ini];
res %= mod;
return res;
}
lli Rbinaria(lli ini, lli fin, lli pa, lli pb, lli ind) {
lli mitad,a,b,sa,sb,dist = 0;
while (ini <= fin) {
mitad = (ini+fin)/2;
a = pa+mitad;
b = pb+mitad;
sa = query(pa,a,0);
sb = query(pb,b,ind);
if (sa == sb){
dist = mitad;
ini = mitad+1;
}
else fin = mitad-1;
}
return dist;
}
lli Ibinaria(lli ini, lli fin, lli pa, lli pb, lli ind) {
lli mitad,a,b,sa,sb,dist = 0;
while (ini <= fin) {
mitad = (ini+fin)/2;
a = pa-mitad;
b = pb-mitad;
sa = query(a,pa,0);
sb = query(b,pb,ind);
if (sa == sb){
dist = mitad;
ini = mitad+1;
}
else fin = mitad-1;
}
return dist;
}
str solve(lli pa, lli pb, lli ind) {
lli MIN = min(tam[0]-pa-1, tam[ind]-pb-1);
lli der = Rbinaria(1,MIN,pa,pb,ind);
lli r1 = 0;
lli r2 = 0;
MIN = min(pb, tam[0] - (pa + der) - 1);
repa(i, MIN, 1) {
lli q = query(pa + der + 1, pa + der + MIN, 0);
lli w = query(pb - i, pb - 1, ind);
if (q == w) {
r1 = i;
break;
}
}
MIN = min(pa, tam[ind] - (pb + der) - 1);
repa(i, MIN, 1) {
lli q = query(pb + der + 1, pb + der + MIN, ind);
lli w = query(pa - i, pa - 1, 0);
if (q == w) {
r2 = i;
break;
}
}
str devolver;
devolver.val = der+1+max(r1,r2);
if (r1 > r2){
devolver.a = pa;
devolver.b = pb - r1;
if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);
}
else {
devolver.a = pa - r2;
devolver.b = pb;
if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);
}
//debugsl(devolver.val);
//debugsl(devolver.a);
//debug(devolver.b);
return devolver;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> st[0] >> st[1];
st[2] = st[1];
reverse(st[2].begin(), st[2].end());
tam[0] = st[0].size();
tam[1] = tam[2] = st[1].size();
rep(z,0,2) {
pot[0] = 1;
rep(i,0,tam[z]-1){
k = st[z][i] - 'a';
k++;
k *= pot[i];
acu[z][i] = k;
if (i > 0) acu[z][i] += acu[z][i-1];
acu[z][i] %= mod;
pot[i+1] = pot[i]*prim;
pot[i+1] %= mod;
}
}
inverso();
lli a,b,c,d,ind;
//while (a != -1) {
// cin >> a >> b >> c >> d >> ind;
// if (a == -1) break;
// cout << query(a,b,0) << endl;
// cout << query(c,d,ind) << endl;
//}
rep(pp,0,tam[0]-1) {
rep(ss,0,tam[1]-1){
if (st[0][pp] == st[1][ss]) {
x = solve(pp,ss,1);
if (x.val > res.val) res = x;
sss = tam[1]-ss-1;
x = solve(pp,sss,2);
if (x.val > res.val) res = x;
}
}
}
cout << res.val << "\n";
cout << res.a << ' ' << res.b;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:180:9: warning: unused variable 'a' [-Wunused-variable]
180 | lli a,b,c,d,ind;
| ^
necklace.cpp:180:11: warning: unused variable 'b' [-Wunused-variable]
180 | lli a,b,c,d,ind;
| ^
necklace.cpp:180:13: warning: unused variable 'c' [-Wunused-variable]
180 | lli a,b,c,d,ind;
| ^
necklace.cpp:180:15: warning: unused variable 'd' [-Wunused-variable]
180 | lli a,b,c,d,ind;
| ^
necklace.cpp:180:17: warning: unused variable 'ind' [-Wunused-variable]
180 | lli a,b,c,d,ind;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Partially correct |
4 ms |
320 KB |
Output is partially correct |
| 4 |
Correct |
3 ms |
332 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Partially correct |
4 ms |
320 KB |
Output is partially correct |
| 4 |
Correct |
3 ms |
332 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 6 |
Partially correct |
236 ms |
332 KB |
Output is partially correct |
| 7 |
Partially correct |
124 ms |
332 KB |
Output is partially correct |
| 8 |
Correct |
294 ms |
332 KB |
Output is correct |
| 9 |
Partially correct |
183 ms |
336 KB |
Output is partially correct |
| 10 |
Partially correct |
25 ms |
352 KB |
Output is partially correct |
| 11 |
Partially correct |
28 ms |
348 KB |
Output is partially correct |
| 12 |
Correct |
218 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Partially correct |
4 ms |
320 KB |
Output is partially correct |
| 4 |
Correct |
3 ms |
332 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 6 |
Partially correct |
236 ms |
332 KB |
Output is partially correct |
| 7 |
Partially correct |
124 ms |
332 KB |
Output is partially correct |
| 8 |
Correct |
294 ms |
332 KB |
Output is correct |
| 9 |
Partially correct |
183 ms |
336 KB |
Output is partially correct |
| 10 |
Partially correct |
25 ms |
352 KB |
Output is partially correct |
| 11 |
Partially correct |
28 ms |
348 KB |
Output is partially correct |
| 12 |
Correct |
218 ms |
332 KB |
Output is correct |
| 13 |
Execution timed out |
1576 ms |
332 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
