Submission #867047

#TimeUsernameProblemLanguageResultExecution timeMemory
867047serifefedartarNecklace (Subtask 1-3) (BOI19_necklace1)C++17
85 / 85
176 ms604 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9+9; const ll P = 31; const ll LOGN = 20; const ll MAXN = 1e5 + 5; int ans[3], n, m; int p1[MAXN], p2[MAXN]; 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() { fast string s, t; cin >> s >> t; n = s.size(), m = t.size(); solve(s, t, 0); reverse(t.begin(), t.end()); solve(s, t, 1); cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...