Submission #403266

#	Time	Username	Problem	Language	Result	Execution time	Memory
403266		rama_pang	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1596 ms	1456 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

class Trie {
 public:
  vector<int> sl; // suffix link
  vector<int> len; // length of current node
  vector<array<int, 26>> go; // transition

  int NewNode() {
    sl.emplace_back(0);
    len.emplace_back(0);
    go.emplace_back(array<int, 26>());
    return int(sl.size()) - 1;
  }

  void Insert(string s) {
    int u = 0;
    for (auto c : s) {
      if (!go[u][c - 'a']) {
        int n = NewNode();
        go[u][c - 'a'] = n;
      }
      u = go[u][c - 'a'];
    }
  }

  void Build() {
    for (queue<int> q({0}); !q.empty(); q.pop()) {
      int u = q.front();
      for (int i = 0; i < 26; i++) {
        int v = go[u][i]; go[u][i] = 0;
        if (v) {
          sl[v] = go[sl[u]][i];
          len[v] = len[u] + 1;
          go[u][i] = v;
          q.emplace(v);
        } else {
          go[u][i] = go[sl[u]][i];
        }
      }
    }
  }

  Trie(string str) {
    NewNode(); // initialize root
    Insert(str);
    Build();
  }
};

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

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

  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]);
      }

      Trie trie(str);
      for (int t = 0, i = 0; t < M; t++) {
        i = trie.go[i][T[t] - 'a'];
        dp[t] = max(dp[t], trie.len[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: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40