#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
struct HSH {
HSH(int mod, int key) : MOD(mod), KEY(key) {}
const int MOD, KEY;
int T[3005];
int A[3005], B[3005];
int getA(int s, int e) {
return ((A[e] - ll(T[e-s+1]) * A[s-1]) % MOD + MOD) % MOD;
}
int getB(int s, int e) {
return ((B[s] - ll(T[e-s+1]) * B[e+1]) % MOD + MOD) % MOD;
}
bool cmp(int a, int b, int l) {
return getA(a, a+l-1) == getB(b, b+l-1);
}
} hsh(1000002173, 6481);
char A[3005], B[3005];
int AnsL, AnsI, AnsJ;
int N, M;
bool __isrev;
void upd(int l, int as, int bs) {
if(l <= AnsL) return;
AnsL = l;
AnsI = __isrev ? N-as-l+2 : as;
AnsJ = bs;
}
void precal(HSH &hsh) {
const int MOD = hsh.MOD, KEY = hsh.KEY;
hsh.T[0] = 1;
for(int i = 1; i < 3005; i++)
hsh.T[i] = ll(hsh.T[i-1]) * KEY % MOD;
for(int i = 1; i <= N; i++)
hsh.A[i] = (ll(hsh.A[i-1]) * KEY + (A[i]-'a')) % MOD;
for(int i = M; i; i--)
hsh.B[i] = (ll(hsh.B[i+1]) * KEY + (B[i]-'a')) % MOD;
}
int LH[3005], RH[3005];
int L[3005], R[3005];
void process() {
precal(hsh);
for(int delta = -N+1; delta <= M-1; delta++) {
memset(L, 0, 3005<<2);
memset(R, 0, 3005<<2);
// TODO
for(int i = 1; i <= N; i++) {
{
int mxl = -1;
int s = 0, e = N; for(int m, as, ae, bs, be; s <= e;) {
m = (s+e) >> 1;
as = i - m; ae = i + m;
bs = as + delta; be = ae + delta;
if(as < 1 || N < ae || bs < 1 || M < be || !hsh.cmp(as, bs, m<<1|1)) e = m-1;
else {
if(mxl < m) mxl = m;
s = m+1;
}
}
if(0 <= mxl) {
upmax(LH[i+mxl+1], mxl<<1|1);
upmax(RH[i-mxl], mxl<<1|1);
}
}
{
int mxl = -1;
int s = 0, e = N; for(int m, as, ae, bs, be; s <= e;) {
m = (s+e) >> 1;
as = i - m; ae = i + m + 1;
bs = as + delta; be = ae + delta;
if(as < 1 || N < ae || bs < 1 || M < be || !hsh.cmp(as, bs, (m+1)<<1)) e = m-1;
else {
if(mxl < m) mxl = m;
s = m+1;
}
}
if(0 <= mxl) {
upmax(LH[i+mxl+2], (mxl+1)<<1);
upmax(RH[i-mxl], (mxl+1)<<1);
}
}
}
for(int i = max(N, M), h = 0; i; i--) {
upmax(h, LH[i]);
L[i] = h;
h -= 2;
if(h < 0) h = 0;
}
for(int i = 1, h = 0; i <= max(N, M); i++) {
upmax(h, RH[i]);
R[i] = h;
h -= 2;
if(h < 0) h = 0;
}
for(int i = 1; i <= N; i++)
upd(L[i] + R[i], i-L[i], i-L[i]+delta);
}
}
int main() {
scanf(" %s %s", A+1, B+1);
N = strlen(A+1);
M = strlen(B+1);
for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++)
if(A[i] == B[j]) upd(1, i, j);
process();
reverse(A+1, A+N+1);
__isrev = true;
process();
cout << AnsL << endl << AnsI-1 << " " << AnsJ-1 << endl;
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s %s", A+1, B+1);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
