#include <bits/stdc++.h>
using namespace std;
const int N=3005;
char s[N],t[N];
int kmp[N],n,m;
void Build(){
for(int i=2,j=0;i<=m;i++){
while(j&&t[i]!=t[j+1])j=kmp[j];
if(t[i]==t[j+1])j++;
kmp[i]=j;
}
}
void Go(int ans[]){
for(int i=1,j=0;i<=n;i++){
while(j&&s[i]!=t[j+1])j=kmp[j];
if(s[i]==t[j+1])j++;
ans[i]=j;
}
}
int fw[N],bw[N];
array<int,3> Solve(){
array<int,3> ans={0,0,0};
for(int w=1;w<=m;w++){
Build();Go(fw);
reverse(t+1,t+1+m);
reverse(s+1,s+1+n);
Build();Go(bw);
reverse(t+1,t+1+m);
reverse(s+1,s+1+n);
reverse(bw+1,bw+1+n);
for(int i=1;i<=n;i++){
int now=min(fw[i],m-w+1)+min(bw[i+1],w-1);
if(ans[0]<now){
ans={now,i-min(fw[i],m-w+1),w-min(bw[i+1],w-1)-1};
}
}
char tmp=t[1];
for(int i=2;i<=m;i++)t[i-1]=t[i];
t[m]=tmp;
}
return ans;
}
int main(){
scanf("%s %s",s+1,t+1);
n=strlen(s+1);
m=strlen(t+1);
auto ans1=Solve();
reverse(t+1,t+1+m);
auto ans2=Solve();
ans2[2]=m-ans2[2]-ans2[0];
if(ans1[0]>ans2[0])printf("%i\n%i %i\n",ans1[0],ans1[1],ans1[2]);
else printf("%i\n%i %i\n",ans2[0],ans2[1],ans2[2]);
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s %s",s+1,t+1);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
504 KB |
Output is correct |
| 2 |
Correct |
256 ms |
504 KB |
Output is correct |
| 3 |
Correct |
332 ms |
384 KB |
Output is correct |
| 4 |
Correct |
233 ms |
384 KB |
Output is correct |
| 5 |
Correct |
201 ms |
384 KB |
Output is correct |
| 6 |
Correct |
227 ms |
480 KB |
Output is correct |
| 7 |
Correct |
248 ms |
384 KB |
Output is correct |
| 8 |
Correct |
270 ms |
384 KB |
Output is correct |
| 9 |
Correct |
285 ms |
384 KB |
Output is correct |
