Submission #403273

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403273	2021-05-13T01:10:43 Z	rama_pang	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	333 ms	484 KB

necklace

#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

#	Verdict	Execution time	Memory	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