Đề bài
Cho 2 xâu ký tự . Tìm cách cắt xâu thành các xâu con liên tiếp sao cho trong số các xâu con được tạo ra, số lần xuất hiện của xâu là nhiều nhất có thể.
Dữ liệu vàoCUT.INP
Đọc vào từ file CUT.INP
- Dòng đầu tiên chứa xâu độ dài không quá ký tự.
- Dòng thứ hai chứa xâu độ dài không quá 10 ký tự.
Các ký tự xuất hiện trong 2 xâu đều là các chữ cái latin in thường.
Kết quả raCUT.OUT
Ghi ra file CUT.OUT một số nguyên là số lần xuất hiện nhiều nhất của xâu P trong cách cắt tìm được.
Ràng buộc
- Có 50% số test tương ứng 50% số điểm có độ dài xâu không vượt quá và xâu chỉ gồm 1 ký tự.
- Có 30% số test khác tương ứng 30% số điểm có độ dài xâu không vượt quá .
- Có 20% số test còn lại tương ứng 20% số điểm có độ dài xâu không quá
Ví dụ
Ví dụ 1
hungyenhyhy h
3
Giải thích
Ta cắt xâu = h + ungyen + h + y + h + y
Ví dụ 2
mmumumumm mum
2
Giải thích
Ta cắt xâu = m + mum + u + mum + m . Trong trường hợp này, xâu xuất hiện tại 3 vị trí trong , tuy nhiên khi cắt xâu chỉ có thể tạo thành tối đa 2 xâu