#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define maxn 3005
int n,m,dp[maxn],len,apos,bpos,_len,_apos,_bpos;
int lps[maxn],flen[maxn],rlen[maxn];
char a[maxn],b[maxn];
void solve(int split,int &len,int &apos,int &bpos){
for(int i=0;i<=n;++i)flen[i]=rlen[i]=0;
for(int i=0;i<=m;++i)lps[i]=0;
//kmp algorithm
for(int i=1,pos=0;i<split;){
if(b[i]==b[pos])lps[i++]=++pos;
else if(pos>0)pos=lps[pos-1];
else ++i;
}
lps[split]=split;
for(int i=split+1,pos=split;i<m;){
if(b[i]==b[pos])lps[i++]=++pos;
else if(pos>split)pos=lps[pos-1];
else pos=split,++i;
}
//printf("\nsplit %d\n",split);
//printf("%s\n",b);
//pf("lps: ");for(int i=0;i<m;++i)pf("%d ",lps[i]);pf("\n");
for(int i=0,j=split;i<n;){
if(j<m&&a[i]==b[j])flen[i++]=++j-split;
else if(j>split)j=lps[j-1];
else ++i;
}
//pf("flen: ");for(int i=0;i<m;++i)pf("%d ",flen[i]);pf("\n");
for(int i=n-1,j=0;i>=0;){
if(j<split&&a[i]==b[j])rlen[i--]=++j;
else if(j>0)j=lps[j-1];
else --i;
}
//pf("rlen: ");for(int i=0;i<m;++i)pf("%d ",rlen[i]);pf("\n");
for(int i=0;i<=n;++i){
//printf("%d: %d\n",i,(i?flen[i-1]:0)+(i<n?rlen[i]:0));
if((i?flen[i-1]:0)+(i<n?rlen[i]:0)>len){
len=(i?flen[i-1]:0)+(i<n?rlen[i]:0);
//printf("%d %d\n",flen[i-1],rlen[i]);
apos=i-(i?flen[i-1]:0);
bpos=split-(i<n?rlen[i]:0);
//printf("%d %d\n",apos,bpos);
}
}
}
void solve(bool rev){
for(int i=0;i<=m;++i){
reverse(b,b+i);
//original string is abcdef
//reverse first part of string --> cba + def
//match each string with some part of other string
solve(i,_len,_apos,_bpos);
if(_len>len){
len=_len,apos=_apos,bpos=_bpos;
//pf("%d %d\n",apos,bpos);
if(rev)bpos=m-bpos-len;
}
reverse(b,b+i);
}
}
int main(){
sf(" %s",&a);sf(" %s",&b);
n=strlen(a),m=strlen(b);
solve(0);
reverse(b,b+m);
solve(1);
pf("%d\n%d %d\n",len,apos,bpos);
}
/*
zxyabcd
yxbadctz
zxyabcd
xtcdabxy
*/
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:77:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3005]' [-Wformat=]
77 | sf(" %s",&a);sf(" %s",&b);
| ~^ ~~
| | |
| | char (*)[3005]
| char*
necklace.cpp:77:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3005]' [-Wformat=]
77 | sf(" %s",&a);sf(" %s",&b);
| ~^ ~~
| | |
| | char (*)[3005]
| char*
necklace.cpp:77:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | sf(" %s",&a);sf(" %s",&b);
| ^
necklace.cpp:77:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | sf(" %s",&a);sf(" %s",&b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
340 KB |
Output is correct |
| 2 |
Correct |
141 ms |
340 KB |
Output is correct |
| 3 |
Correct |
227 ms |
340 KB |
Output is correct |
| 4 |
Partially correct |
124 ms |
328 KB |
Output is partially correct |
| 5 |
Correct |
132 ms |
340 KB |
Output is correct |
| 6 |
Partially correct |
129 ms |
340 KB |
Output is partially correct |
| 7 |
Correct |
148 ms |
340 KB |
Output is correct |
| 8 |
Correct |
158 ms |
340 KB |
Output is correct |
| 9 |
Correct |
169 ms |
340 KB |
Output is correct |
