Tìm chuỗi con mẫu có thứ tự

Xem dưới dạng PDF
Gửi bài giải
Điểm: 10
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
🌸You
Kiểu bài tập

Cho chuỗi \(s0\) có thứ tự (các ký tự giống nhau sẽ đứng kế nhau), hệ thống sẽ mã hóa chuỗi \(s0\) ban đầu thành chuỗi \(s1\) bằng cách sinh ngẫu nhiên các ký tự và chèn vào các vị trí bất kỳ của chuỗi \(s0\). Các bạn hãy lập trình để tính toán số bước nhỏ nhất để có thể chuyển chuỗi \(s1\) về lại chuỗi \(s0\) bằng cách chọn chuỗi con nhỏ nhất của \(s1\) mà có chứa \(s0\), sau đó xóa các ký tự cần thiết để chuyển chuỗi con đó về lại \(s0\).

Dữ liệu vào: 2 chuỗi s1 và s0 (các ký tự trong chuỗi có giá trị từ \(A-Z\))

Dữ liệu ra: số bước nhỏ nhất nếu không tìm được thì in \(-1\)

Scoring

  • Subtask 1 (\(20%\) số điểm): \(n \le 21\)
  • Subtask 2 (\(30%\) số điểm): \(n \le 3 \times 10^3\)
  • Subtask 3 (\(30%\) số điểm): \(n \le 2 \times 10^5\)
  • Subtask 4 (\(20%\) số điểm): Không ràng buộc gì thêm

Input

LLDLQDQDDL LLQQDD

Output

2

Giải thích

Chọn xâu con LDLQDQDD, bỏ ký tự thứ \(2\) và \(5\) tính từ trái qua sẽ thu được xâu LLQQDD là xâu ban đầu mà hệ thống sinh ra.

Nhận xét