#include<bits/stdc++.h>
using namespace std;
string s,ss;
int n,m;
const int maxn=3000+10;
int lcp[maxn],fkmp[maxn],revfkmp[maxn];
string fake;
vector<int>kmp;
void findkmp(int mid){
for(int i=0;i<maxn;i++){
revfkmp[i]=fkmp[i]=0;
}
fake.clear();
for(int i=mid;i<n;i++){
fake.push_back(s[i]);
}
fake.push_back('$');
int len=fake.size();
fake+=ss;
kmp.clear();
kmp.resize((int)fake.size()+10);
for(int i=1;i<(int)fake.size();i++){
int now=kmp[i-1];
while(now>=0){
if(fake[i]==fake[now]){
break;
}
if(now==0){
now=-1;
break;
}
now=kmp[now-1];
}
now++;
kmp[i]=now;
if(i>=len){
fkmp[i-len]=now;
}
}
fake.clear();
for(int i=mid-1;i>=0;i--){
fake.push_back(s[i]);
}
fake.push_back('$');
len=fake.size();
reverse(ss.begin(),ss.end());
fake+=ss;
reverse(ss.begin(),ss.end());
kmp.clear();
kmp.resize((int)fake.size()+10);
for(int i=1;i<(int)fake.size();i++){
int now=kmp[i-1];
while(now>=0){
if(fake[now]==fake[i]){
break;
}
if(now==0){
now=-1;
break;
}
now=kmp[now-1];
}
now++;
kmp[i]=now;
if(i>=len){
revfkmp[m-1-(i-len)]=now;
}
}
}
pair<int,pair<int,int>> solve(){
n=s.size(),m=ss.size();
pair<int,pair<int,int>>res;
for(int i=0;i<maxn;i++){
lcp[i]=0;
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<m;j++){
if(s[i]==ss[j]){
lcp[j]=lcp[j+1]+1;
}
else{
lcp[j]=0;
}
//cout<<i<<" "<<j<<" "<<lcp[j]<<"\n";
if(res.first<lcp[j]){
res=make_pair(lcp[j],make_pair(i,j));
}
}
}
for(int i=1;i<n;i++){
findkmp(i);
for(int h=1;h<m;h++){
// if(i==3){
// cout<<h<<" "<<fkmp[h-1]<<" "<<revfkmp[h]<<"\n";
// }
if(fkmp[h-1]+revfkmp[h]>res.first){
//cout<<"wtf "<<fkmp[h-1]<<" "<<revfkmp[h]<<" "<<fkmp[h-1]+revfkmp[h]<<" "<<i<<" "<<h<<"\n";
res=make_pair(fkmp[h-1]+revfkmp[h],make_pair(i-revfkmp[h],h-kmp[h-1]));
}
}
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s>>ss;
auto res=solve();
reverse(ss.begin(),ss.end());
auto res2=solve();
//cout<<res2.second.second<<"\n";
if(res2.first>res.first){
swap(res2,res);
res.second.second=m-(res.second.second+res.first-1)-1;
}
cout<<res.first<<"\n";
cout<<res.second.first<<" "<<res.second.second<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
