#include<bits/stdc++.h>
using namespace std;
string s,ss;
const int maxn=3000+10;
int lcp[maxn][maxn],fkmp[maxn][maxn],maxa[maxn][maxn];
int n,m;
void findlcp(){
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
lcp[i][j]=0;
}
}
for(int i=n-1;i>=0;i--){
for(int j=m-1;j>=0;j--){
if(s[i]==ss[j]){
lcp[i][j]=lcp[i+1][j+1]+1;
}
}
}
}
void findkmp(){
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
fkmp[i][j]=0;
}
}
for(int i=0;i<n;i++){
string fake;
for(int j=i;j<n;j++)
{
fake.push_back(s[j]);
}
fake.push_back('@');
fake+=ss;
int len=n-i;
// if(i==5){
// cout<<fake<<"\n";
// }
vector<int>kmp(fake.size()+10);
for(int j=1;j<(int)fake.size();j++){
int now=kmp[j-1];
while(true){
if(fake[j]==fake[now]){
break;
}
if(now==0){
now=-1;
break;
}
now=kmp[now];
}
now++;
kmp[j]=now;
if(j>len){
fkmp[i][j-len-1]=now;
}
// cout<<len<<" "<<j<<" "<<kmp[j]<<"\n";
}
}
}
void findmaxa(){
for(int i=0;i<=m;i++){
maxa[i][0]=fkmp[0][i]+0;
for(int j=1;j<n;j++){
maxa[i][j]=max(maxa[i][j-1],fkmp[j][i]+j);
}
}
}
pair<int,pair<int,int>> solve(){
n=s.size(),m=ss.size();
findlcp();
findkmp();
findmaxa();
//cout<<lcp[3][4]<<" "<<maxa[3][5]<<"\n";
pair<int,pair<int,int>>res;
res.first=0;
res.second=make_pair(0,0);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(lcp[i][j]>=1){
if(j==0){
res=max(res,make_pair(lcp[i][j],make_pair(i,j)));
}
int lasta=maxa[j-1][i+lcp[i][j]]-1;
// if(i==3&&j==4){
// cout<<lasta<<"\n";
// }
res=max(res,make_pair(lasta-i+1,make_pair(i,j-1-(lasta-(i+lcp[i][j]-1))+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();
if(res2.first>res.first){
swap(res2,res);
res.second.second=m-res.second.second-1;
}
res.second.first++;
res.second.second++;
cout<<res.first<<"\n";
cout<<res.second.first<<" "<<res.second.second<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1577 ms |
71236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1577 ms |
71236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1577 ms |
71236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
