Cho hai xâu S và T. Mỗi lần bạn được chọn một tiền tố không rỗng bất kỳ của S; cùng một tiền tố có thể được dùng nhiều lần. Hãy tìm số mảnh ít nhất để ghép theo thứ tự thành đúng T, hoặc in −1 nếu không thể.
Input
Dòng đầu chứa S, dòng thứ hai chứa T.
Output
In số mảnh nhỏ nhất, hoặc −1 nếu không có cách.
Constraints
1≤∣S∣,∣T∣≤5⋅105.
Hai xâu chỉ gồm chữ thường.
Scoring
Subtask 1 (50%): Tổng độ dài không vượt 2000.
Subtask 2 (50%): Không có giới hạn bổ sung.
Example
Test 1
Input
aba
ababa
Output
2
Giải thích: Chọn tiền tố ab, sau đó chọn tiền tố aba; ghép lại được ababa. Chỉ một mảnh không đủ vì T dài hơn S.
Lời giải tóm tắt
Ý tưởng: Gọi match[i] là độ dài tiền tố lớn nhất của S trùng T[i..], lấy trực tiếp từ Z. Ta cần đi từ vị trí 0 đến |T|; từ một vị trí đã tới được i, một mảnh cho phép tới mọi vị trí trong (i, i+match[i]].
Ý tưởng: Xử lý theo các lớp BFS trên trục số. layerRight là vị trí xa nhất đạt được với số mảnh hiện tại; quét mọi điểm mới của lớp để lấy farthest = max(i+match[i]). Nếu không tiến thêm được thì in -1; mỗi lần mở rộng một lớp là dùng thêm đúng một mảnh.
Chứng minh đúng: Quy nạp theo số mảnh: sau k lớp, đoạn [0, layerRight] đúng là toàn bộ các vị trí có thể đạt bằng không quá k mảnh. Từ mọi vị trí trong lớp hiện tại, Z liệt kê chính xác khoảng đích của một mảnh tiếp theo, nên cực đại farthest là biên xa nhất của lớp k+1. Lần đầu chạm cuối T vì thế dùng số mảnh nhỏ nhất.
Độ phức tạp:O(|S|+|T|) thời gian và bộ nhớ.
Mẫu công khai: Đường đi 0→2→5 dùng hai mảnh; không có cạnh trực tiếp 0→5.