Bình luận

• 
  

  13

  SPyofgame    6:47 p.m. 29 Tháng 4, 2021 ← đã chỉnh sửa →

  Thi thử duyên hải 2021 lần hai bài Khóa then chốt

• 
  

  15

  SPyofgame    7:18 p.m. 29 Tháng 4, 2021 ← chỉnh sửa 2 →

  ---

  \(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

  \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

  \(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

  ---

  ---

  \(\color{orange}{\text{Hướng dẫn}}\)

  • Nhận xâu \(T[1 \dots n]\) từ đầu vào. Ta cần tìm một xâu \(S\) thỏa

  [1] \(S = T[L\dots R]\) với \(1 \leq L \leq R \leq N\)

  [2] \(T[i] = T[n - i + 1]\ \ \forall\ \ i = L \dots R\)

  Trong các xâu thỏa mãn, ta chọn xâu có độ dài lớn nhất (yêu cầu đề)

  • Chứng minh

  Với \(m\) là một hằng số nào đó

  Có \(T_1, T_2, \dots, T_{L-1}\) là \(m\) kí tự được thêm vào trước

  Có \(T_n, T_{n-1}, \dots, T_{n - L}\) là \(m\) kí tự được thêm vào sau

  Gọi \(P = T[L\dots n - L + 1]\) là xâu trước khi thêm \(m\) kí tự ngẫu nhiên vào trước sau.

  Thì từ [1] ta có \(S\) là tiền tố của \(P\) và từ [2] ta có nghịch đảo của \(S\) cũng là hậu tố của \(P\)

  ---

  \(\color{goldenrod}{\text{Tiếp cận}}\)

  • Trâu: Thử các đoạn \([L \dots R]\)

  Có tất cả \(O(n^2)\) cách chọn vị trí và \(O(n)\) để thử mỗi lần tổng cộng là \(O(n^3)\)

  Tối ưu hơn thì khi ta vừa duyệt ta vừa kiểm tra, nếu có một vị trí không thỏa thì cả đoạn không thỏa, bằng cách này chỉ còn \(O(n^2)\)

  • Chặt nhị phân và hash: Từ mỗi vị trí \(L\) tìm vị trí \(R\) lớn nhất thỏa điều kiện đề

  Có \(O(n)\) cách chọn vị trí \(L\)

  Chặt nhị phân tìm kiếm sẽ mất \(O(log)\)

  Để kiểm tra 2 đoạn xâu bằng nhau không ta mất \(O(log)\) với tiền xử lí hash

  Vậy là \(O(n log^2(n))\) với \(O(n log(MOD))\) tiền xử lí

  Có thể tối ưu lên \(O(n log n)\) với \(O(n + log(MOD))\) tiền xử lí

  • Hai con trỏ: Trong khi tính chất còn thỏa thì tăng \(R\), ngược lại tăng \(L\)

  Mỗi lần tăng \(R\) giảm \(L\) ta chỉ cần kiểm tra trong \(O(1)\)

  Nhận thấy rằng nếu \(R\) không thỏa thì cả đoạn \([L \dots R]\) không thỏa và \([P \dots R - 1]\) có độ dài nhỏ hơn \([L \dots R - 1]\) (\(\ \forall\ L \leq P \leq R - 1\)) nên ta có thể dịch \(L\) tới $R + 1 $ luôn

  ---

  \(\color{green}{\text{Code tham khảo }}\): Hai con trỏ

  \(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

  C++

  int query()
  {
      string s;
      cin >> s;
      int n = s.size();
      string t(s.rbegin(), s.rend());
  
      int best_l = 0, best_r = -1;
      for (int l = 0, r = 0; l < n; l = max(l, r) + 1)
      {
          for (r = l - 1; r + 1 < n && s[r + 1] == t[r + 1]; ++r);
  
          if (best_r - best_l < r - l)
          {
              best_l = l;
              best_r = r;
          }
      }
  
      cout << s.substr(best_l, best_r - best_l + 1) << '\n';
      return 0;
  }
  
4 bình luận nữa