Xóa Ký Tự Trong Chuỗi

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho chuỗi $S$ độ dài $N$ và chuỗi $T$ độ dài $M$ . Hãy xóa số ký tự tối thiểu từ $S$ sao cho $T$ không xuất hiện là một xâu con liên tiếp trong chuỗi còn lại.

Dữ liệu vào

Dòng 1: Chuỗi $S$ gồm các chữ cái thường
Dòng 2: Chuỗi $T$ gồm các chữ cái thường

Dữ liệu ra

Số nguyên: số ký tự tối thiểu cần xóa.

Ràng buộc

$1 \leq M \leq N \leq 10000$
$M \leq 1000$
Tất cả ký tự là chữ cái thường (a-z)

Ví dụ

Input	Output	Giải thích
ababaa aba	1	Xóa ký tự tại vị trí 2 (b), được "abaa". Kiểm tra: "aba" không xuất hiện trong "abaa".

Bình luận

Không có bình luận tại thời điểm này.