Submit solution
Points:
0.01 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Authors:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho hai xâu ~X~ và ~Y~ chỉ gồm các kí tự in thường. Trong một thao tác, bạn có thể chọn một kí tự bất kì trên xâu ~X~ và xóa nó đi. Đếm số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~ nữa.
Định nghĩa xâu ~A~ gọi là xuất hiện trong xâu ~B~ nếu tồn tại vị trí ~i~ (~1 \leq i \leq |B| - |A| + 1~) mà ~A_j = B_{i + j - 1} \forall j \in [1, |A|]~, ở đây mỗi kí tự được đánh chỉ số từ ~1~ từ trái qua phải và ~|t|~ là độ dài của xâu ~t~.
Input
Gồm ~3~ testcase, mỗi testcase trên hai dòng.
Dòng đầu tiên chứa xâu ~X~ (~1\leq |X| \leq 10^4~).
Dòng thứ hai chứa xâu ~Y~ (~1 \leq |Y| \leq 10^3~).
Output
Gồm ~3~ dòng, mỗi dòng in ra một số duy nhất là số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~.
Sample Input 1
hhhhh
h
xywpywtddh
yw
cyapyaa
ya
Sample Output 1
5
2
2
Comments