| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1261392 | ebrambill | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 0 ms | 0 KiB |
//In the name of GOD
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,O3")
#include <bits/stdc++.h>
using namespace std;
const short int maxN=3e3+5;
short int n, m, lps[maxN][maxN], tmp[maxN<<1]={-1}, ans, Ct, Cs;
string s, t, ts;
void solve(bool rt, bool rs){
for (short int i=m; i>=1; i--){
for (short int j=i, cur=j-1; j<=n+m+1; j++, cur=j-1){
while(ts[tmp[cur-i+1]+i]!=ts[j] and tmp[cur-i+1]>=0) cur=tmp[cur-i+1]+i-1;
tmp[j-i+1]=tmp[cur-i+1]+1;
if(j>m+1) lps[i][j-m-1]=tmp[j-i+1];
}
for (short int j=1; j<=n; j++){
short int x=lps[i][j]+lps[i+lps[i][j]][j-lps[i][j]];
if(x>ans) ans=x, Ct=(!rt ? i-1 : m-i-x+1), Cs=(!rs ? j-x : n-j);
}
}
}
int main(){
cin >>s >>t;
n=s.size(), m=t.size();
ts='.'+t+'.'+s;
solve(false, false);
reverse(ts.begin()+m+2, ts.end());
solve(false, true);
reverse(ts.begin()+1, ts.begin()+m+1);
solve(true, true);
reverse(ts.begin()+m+2, ts.end());
solve(true, false);
cout <<ans <<endl <<Cs <<' ' <<Ct;
}