Submission #403108

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

necklace

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

class HashString {
 public:
  const int KEY = 37;
  const int MOD = 1e9 + 9;

  int N;
  string S;
  vector<int> H;

  vector<int> power;
  vector<int> inv_power;

  HashString(string S) : S(S) {
    N = S.size();
    H.resize(N);
    power.resize(N);
    inv_power.resize(N);

    const auto Power = [&](int a, int x) {
      int z = 1;
      while (x) {
        if (x & 1) z = 1ll * z * a % MOD;
        x /= 2;
        a = 1ll * a * a % MOD;
      }
      return z;
    };

    power[0] = inv_power[0] = 1;
    power[1] = KEY;
    inv_power[1] = Power(KEY, MOD - 2);
    for (int i = 2; i < N; i++) {
      power[i] = 1ll * KEY * power[i - 1] % MOD;
      inv_power[i] = 1ll * inv_power[i - 1] * inv_power[1] % MOD;
    }

    for (int i = 0; i < N; i++) {
      assert(1ll * power[i] * inv_power[i] % MOD == 1);
    }

    for (int i = 0; i < N; i++) {
      H[i] = ((i > 0 ? H[i - 1] : 0) + 1ll * (S[i] - 'a' + 1) * power[i]) % MOD;
    }
  }

  int GetHash(int L, int R) {
    int res = (H[R] + MOD - (L > 0 ? H[L - 1] : 0)) % MOD;
    return 1ll * res * inv_power[L] % MOD;
  }
};

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};
    HashString HS = HashString(S);
    HashString HT = HashString(T);

    // cout << HS.GetHash(2, 3) << ' ' << HT.GetHash(1, 2) << " hm\n";

    for (int t = 0; t < M; t++) {
      vector<int> dp(N);
      // dp[s] = longest suffix of T[0...t-1] which is a prefix of S[s...N]
      for (int s = 0; s < N; s++) {
        int lo = 0, hi = max(N, M);
        while (lo < hi) {
          int md = (lo + hi + 1) / 2;
          if (0 <= s - md + 1 && 0 <= t - md &&
              HS.GetHash(s - md + 1, s) == HT.GetHash(t - md, t - 1)) {
            lo = md;
          } else {
            hi = md - 1;
          }
        }
        // cout << s << ' ' << t << ' ' << lo << " getdp\n"; 
        dp[s - lo + 1] = max(dp[s - lo + 1], lo);
      }
      for (int s = 1; s < N; s++) {
        dp[s] = max(dp[s], dp[s - 1] - 1);
      }

      // cout << "DP: ";
      // for (int s = 0; s < N; s++) {
      //   cout << dp[s] << ' ';
      // }
      // cout << '\n';

      for (int s = 0; s < N; s++) {
        // Get longest common prefix starting with S[s...N], T[t...M]
        int lo = 0, hi = max(N, M);
        while (lo < hi) {
          int md = (lo + hi + 1) / 2;
          if (s + md - 1 < N && t + md - 1 < M &&
              HS.GetHash(s, s + md - 1) == HT.GetHash(t, t + md - 1)) {
            lo = md;
          } else {
            hi = md - 1;
          }
        }

        // S[s...s + lo - 1] == T[t...t + lo - 1]
        // Then, answer is lo + dp[s + lo]
        int len = lo + (s + lo == N ? 0 : dp[s + lo]);
        ans = max(ans, {len, s, t - dp[s + lo]});

        // cout << s << ' ' << t << ' ' << lo << ' ' << dp[s + lo] << " ha\n";
      }
    }

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

  // auto ans = Solve();

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

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40