# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
290090 | alexandra_udristoiu | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 525 ms | 504 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<cstring>
using namespace std;
int n, m, i, j, sol, x, ii, jj, val, nr;
int d[3005], ds[3005], z[6005];
char a[3005], b[3005], s[6005];
void zet(){
int i, ii = 0;
for(i = 2; i <= nr; i++){
if(ii + z[ii] - 1 >= i){
z[i] = min(ii + z[ii] - i, z[i - ii + 1]);
}
else{
z[i] = 0;
}
while(i + z[i] <= nr && s[ z[i] + 1 ] == s[ i + z[i] ]){
z[i]++;
}
if(i + z[i] > ii + z[ii]){
ii = i;
}
}
}
void solve(int t){
for(i = 1; i <= n; i++){
nr = 0;
for(j = i; j <= n; j++){
s[++nr] = a[j];
}
s[++nr] = '*';
for(j = 1; j <= m; j++){
s[++nr] = b[j];
}
zet();
x = m;
for(j = nr; j >= nr - m + 1; j--){
d[x] = z[j];
x--;
}
nr = 0;
for(j = i - 1; j >= 1; j--){
s[++nr] = a[j];
}
s[++nr] = '*';
for(j = m; j >= 1; j--){
s[++nr] = b[j];
}
zet();
memset(ds, 0, sizeof(ds) );
x = m;
for(j = i + 1; j <= nr; j++){
ds[ x - z[j] + 1] = max(z[j], ds[ x - z[j] + 1 ]);
x--;
}
for(j = 1; j <= m; j++){
val = d[j] + ds[ j + d[j] ];
if(val > sol){
sol = val;
if(t == 0){
jj = j;
}
else{
jj = j + val - 1;
jj = m - jj + 1;
}
ii = i - ds[ j + d[j] ];
}
sol = max(sol, d[j] + ds[ j + d[j] ]);
}
}
}
int main(){
cin>> a + 1;
n = strlen(a + 1);
cin>> b + 1;
m = strlen(b + 1);
solve(0);
for(i = 1, j = m; i < j; i++, j--){
swap(b[i], b[j]);
}
solve(1);
cout<< sol <<"\n";
cout<< ii - 1 <<" "<< jj - 1 <<"\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |