Submission #1318638

#TimeUsernameProblemLanguageResultExecution timeMemory
1318638a.pendovNecklace (Subtask 4) (BOI19_necklace4)C++20
15 / 15
255 ms480 KiB
#include<bits/stdc++.h> using namespace std; const short MAXN=6099; short pi1[MAXN],pi2[MAXN]; short ans=0,ansP1,ansP2,M,N; string a,b,currStr; signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); short curr=0; cin>>a>>b; N=a.size(); M=b.size(); for(short i=0;i<=M;i++) { currStr=""; for(short j=i;j<M;j++)currStr.push_back(b[j]); currStr+="#"+a+"&"; for(short j=0;j<i;j++)currStr.push_back(b[j]); memset(pi1,0,sizeof(pi1)); memset(pi2,0,sizeof(pi2)); curr=0; for(short j=1;j<N+M+2;j++) { while(curr>0&&currStr[j]!=currStr[curr])curr=pi1[curr-1]; if(currStr[j]==currStr[curr])curr++; pi1[j]=curr; } reverse(currStr.begin(),currStr.end()); curr=0; for(short j=1;j<N+M+2;j++) { while(curr>0&&currStr[j]!=currStr[curr])curr=pi2[curr-1]; if(currStr[j]==currStr[curr])curr++; pi2[j]=curr; } for(short j=M-i;j<=M+N-i+1;j++) { if(pi1[j]+pi2[M+N-j]>=ans) { ans=pi1[j]+pi2[M+N-j]; ansP1=j-(M-i)-pi1[j]; ansP2=M-(M-i)-pi2[M+N-j]; } } } reverse(b.begin(),b.end()); for(short i=0;i<=M;i++) { currStr=""; for(short j=i;j<M;j++)currStr.push_back(b[j]); currStr+="#"+a+"&"; for(short j=0;j<i;j++)currStr.push_back(b[j]); memset(pi1,0,sizeof(pi1)); memset(pi2,0,sizeof(pi2)); curr=0; for(short j=1;j<N+M+2;j++) { while(curr>0&&currStr[j]!=currStr[curr])curr=pi1[curr-1]; if(currStr[j]==currStr[curr])curr++; pi1[j]=curr; } reverse(currStr.begin(),currStr.end()); curr=0; for(short j=1;j<N+M+2;j++) { while(curr>0&&currStr[j]!=currStr[curr])curr=pi2[curr-1]; if(currStr[j]==currStr[curr])curr++; pi2[j]=curr; } for(short j=M-i;j<=N+M-i+1;j++) { if(pi1[j]+pi2[M+N-j]>=ans) { ans=pi1[j]+pi2[M+N-j]; ansP1=j-(M-i)-pi1[j]; ansP2=M-(M-(M-i)-pi2[M+N-j])-ans; } } } cout<<ans<<endl<<ansP1<<" "<<ansP2<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...