제출 #882091

#제출 시각아이디문제언어결과실행 시간메모리
882091DucNguyen2007Necklace (Subtask 4) (BOI19_necklace4)C++14
15 / 15
147 ms2652 KiB
#include<bits/stdc++.h> using namespace std; const int maxN=1e6+5; #define ll long long #define ben(x) x.begin(),x.end() string s,t; ll ans[3],n,m,p1[maxN+1],p2[maxN+1]; void calc(string s,ll p[]) { ll n=s.length(); p[0]=0; for(int i=1;i<n;i++) { ll j=p[i-1]; while(j>0&&s[i]!=s[j]) { j=p[j-1]; } if(s[i]==s[j]) { j++; } p[i]=j; } } void solve(string s,string t,bool rev) { string t_rev=t; reverse(ben(t_rev)); for(int i=0;i<n;i++) { string l=s.substr(0,i),r=s.substr(i,n); reverse(ben(l)); string a=l+"#"+t; string b=r+"#"+t_rev; calc(a,p1); calc(b,p2); for(int j=1;j<=m;j++) { ll cur1=p1[i+j]; ll cur2=p2[n+m-j-i]; if(cur1+cur2>ans[0]) { ans[0]=cur1+cur2; ans[1]=i-p1[i+j]; if(rev) { ans[2]=m-j-cur2; } else ans[2]=j-cur1; } } } } int main() { cin>>s>>t; n=s.length(),m=t.length(); solve(s,t,0); reverse(ben(t)); solve(s,t,1); cout<<ans[0]<<'\n'<<ans[1]<<" "<<ans[2]; }
#Verdict Execution timeMemoryGrader output
Fetching results...