Submission #882090

#TimeUsernameProblemLanguageResultExecution timeMemory
882090DucNguyen2007Necklace (Subtask 4) (BOI19_necklace4)C++14
0 / 15
167 ms2608 KiB
#include<bits/stdc++.h> using namespace std; const int maxN=1e6+5; #define ll int #define ben(x) x.begin(),x.end() string s,t; ll ans[3],n,m,p1[maxN+1],p2[maxN+1]; void compute(string s, int p_array[]) { int q = s.length(); p_array[0] = 0; for (int i = 1; i < q; i++) { int j = p_array[i-1]; while (j && s[i] != s[j]) j = p_array[j-1]; if (s[i] == s[j]) j++; p_array[i] = j; } } void solve(string s, string t, bool rev) { string t_rev = t; reverse(t_rev.begin(), t_rev.end()); for (int i = 0; i < n; i++) { string l_up = s.substr(0, i), r_up = s.substr(i, n); reverse(l_up.begin(), l_up.end()); string for_a = l_up + "#" + t; string for_b = r_up + "#" + t_rev; compute(for_a, p1); compute(for_b, p2); for (int j = 1; j <= m; j++) { int a = p1[i+j]; int b = p2[n+m-i-j]; if (a + b > ans[0]) { ans[0] = a + b; ans[1] = i - p1[i+j]; ans[2] = (rev ? m - j - b : j - a); } } } } int main() { cin>>s>>t; n=s.length(),m=s.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...