제출 #414707

#제출 시각아이디문제언어결과실행 시간메모리
414707JerryLiu06Necklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
5 ms612 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vd = vector<db>; using vs = vector<str>; using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; #define mp make_pair #define f first #define s second #define sz(x) (int)(x).size() #define bg(x) begin(x) #define all(x) bg(x), end(x) #define sor(x) sort(all(x)) #define ft front() #define bk back() #define pb push_back #define pf push_front #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define R0F(i, a) ROF(i, 0, a) #define EACH(a, x) for (auto& a : x) const int MOD = 1e9 + 7; const int MX = 3010; const ll INF = 1e18; int N, M; string A, B; int DP[MX]; // Description: For every i in [0, N), calculate res[i] be the maximum proper (not equal // to the entire string) prefix of S[0 ... i] that is also a suffix. Complexity: O(N) int maxPref(string S) { F0R(i, sz(S)) DP[i] = 0; int ans = 0; FOR(i, 1, sz(S)) { int j = DP[i - 1]; while (j > 0 && S[i] != S[j]) j = DP[j - 1]; if (S[i] == S[j]) j++; DP[i] = j; } return DP[sz(S) - 1]; } array<int, 3> solve(string S1, string S2, bool rev) { array<int, 3> ans = {0, 0, 0}; F0R(i, N) { string L1 = S1.substr(0, i), R1 = S1.substr(i, N); // cout << L1 << " " << R1 << "\n"; F0R(j, M) { string L2 = S2.substr(j, M), R2 = S2.substr(0, j); int ansL = maxPref(L2 + "#" + L1), ansR = maxPref(R1 + "#" + R2); if (!rev) { ans = max(ans, {ansL + ansR, i - ansL, j - ansR}); } else { ans = max(ans, {ansL + ansR, i - ansL, M - (j + ansL)}); } // cout << ansL + ansR << " " << i << " " << ansL << " " << j << " " << ansR << " " << (L2 + "#" + L1) << " " << (R1 + "#" + R2) << "\n"; } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> A >> B; N = sz(A), M = sz(B); array<int, 3> ans = {0, 0, 0}; ans = max(ans, solve(A, B, false)); reverse(all(B)); ans = max(ans, solve(A, B, true)); cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int maxPref(std::string)':
necklace.cpp:59:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |         if (S[i] == S[j]) j++; DP[i] = j;
      |         ^~
necklace.cpp:59:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |         if (S[i] == S[j]) j++; DP[i] = j;
      |                                ^~
necklace.cpp:56:9: warning: unused variable 'ans' [-Wunused-variable]
   56 |     int ans = 0; FOR(i, 1, sz(S)) {
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...