#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;
}
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;
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;
}
}
str devolver;
devolver.val = der+1+max(r1,r2);
devolver.a = pa;
devolver.b = pb - r1;
if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);
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();
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 'str solve(long long int, long long int, long long int)':
necklace.cpp:98:33: error: 'r2' was not declared in this scope; did you mean 'r1'?
98 | devolver.val = der+1+max(r1,r2);
| ^~
| r1
