oj.uz

답안 #403273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403273 2021-05-13T01:10:43 Z rama_pang Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 333 ms 484 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  string S, T;
  cin >> S >> T;

  const auto GetLink = [&](string s) {
    vector<int> link(s.size() + 1, 0);
    for (int i = 1, j = 0; i < int(s.size()); i++) {
      while (j > 0 && !(j < int(s.size()) && s[i] == s[j])) {
        j = link[j];
      }
      if (j < int(s.size()) && s[i] == s[j]) {
        j += 1;
      }
      link[i + 1] = j;
    }
    return link;
  };

  const auto Solve = [&]() -> array<int, 3> {
    int N = S.size();
    int M = T.size();

    array<int, 3> ans = {0, 0, 0};

    vector<int> lcs(M); // lcs[t] = longest common suffix of S[0...s], T[0...t]
    for (int s = 0; s < N; s++) {
      for (int t = M - 1; t >= 0; t--) {
        if (S[s] == T[t]) {
          lcs[t] = 1 +  (t > 0 ? lcs[t - 1] : 0);
        } else {
          lcs[t] = 0;
        }
      }

      vector<int> dp(M); // dp[t] = longest prefix of S[s+1...N] which is suffix of T[0...t]

      string str;
      for (int i = s + 1; i < N; i++) {
        str.push_back(S[i]);
      }

      vector<int> link = GetLink(str);
      for (int t = 0, i = 0; t < M; t++) {
        while (i > 0 && !(i < int(str.size()) && T[t] == str[i])) {
          i = link[i];
        }
        if (i < int(str.size()) && T[t] == str[i]) {
          i += 1;
        }
        dp[t] = max(dp[t], i);
      }
      for (int t = M - 2; t >= 0; t--) {
        dp[t] = max(dp[t], dp[t + 1] - 1);
      }

      for (int t = 0; t < M; t++) if (lcs[t] > 0) {
        int k = lcs[t] + (t < lcs[t] ? 0 : dp[t - lcs[t]]);
        ans = max(ans, {k, s - lcs[t] + 1, t - k + 1});
      }
    }

    return ans;
  };

  auto ans1 = Solve();
  reverse(begin(T), end(T));
  auto ans2 = Solve();
  ans2[2] = int(T.size()) - ans2[2] - ans2[0];
  auto ans = max(ans1, ans2);

  cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
  return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 384 KB Output is correct
2 Correct 279 ms 484 KB Output is correct
3 Correct 322 ms 476 KB Output is correct
4 Correct 250 ms 332 KB Output is correct
5 Correct 233 ms 452 KB Output is correct
6 Correct 247 ms 484 KB Output is correct
7 Correct 265 ms 380 KB Output is correct
8 Correct 294 ms 384 KB Output is correct
9 Correct 286 ms 352 KB Output is correct