Points:
1500 (p)
Time limit:
0.1s
Memory limit:
256M
Input:
stdin
Output:
stdout
Bạn vừa được tặng một chuỗi hạt nhiều màu rất đẹp!
Để thuận tiện, ta kí hiệu những hạt cùng màu sắc bằng những kí tự giống nhau. Chúng ta sẽ dùng \(26\) kí tự Latin in thường (a
-z
) để biểu diễn các hạt khác màu nhau. Như vậy, chuỗi hạt được tặng có thể biểu diễn dưới dạng một xâu \(S\) có \(n\) kí tự. Chuỗi hạt được gọi là phong thủy nếu nó chứa các hạt màu may mắn theo đúng thứ tự. Gọi \(P\) là chuỗi may mắn (gồm \(m\) kí tự).
Để kiểm tra một chuỗi hạt có phong thủy hay không, ta làm như sau:
- B0: Chọn một hạt làm hạt bắt đầu trong xâu \(s\) và đánh dấu nó.
- B1: Đặt \(i = 1\).
- B2: Nếu \(i > m\) thì kết thúc quá trình tìm kiếm.
- B3: Nếu hạt hiện tại trùng với hạt thứ \(i\) trong chuỗi may mắn, gán \(i = i+1\).
- B4: Lần chuỗi hạt tới vị trí tiếp theo.
- B5: Nếu lần tới hạt được đánh dấu (hạt bắt đầu), ta kết thúc quá trình tìm kiếm vì đã đi được một vòng.
- B6: Quay lại bước 2.
Sau khi thực hiện xong các bước trên, nếu \(i > m\) thì ghi nhận \(S\) là chuỗi phong thủy.
Ví dụ, với \(S =\) dab
, \(P =\) bd
thì \(S\) là chuỗi phong thủy vì:
- Ta bắt đầu tại hạt thứ \(2\) là
a
. a
không trùng với hạt thứ \(i = 1\) trong \(P\), lần chuỗi hạt tới vị trí tiếp theo.b
trùng với hạt thứ \(i = 1\) trong \(P\), ta gán \(i = 2\), sau đó lần chuỗi hạt tới vị trí tiếp theo.d
trùng với hạt thứ \(i = 2\) trong \(P\), ta gán \(i = 3\), lần chuỗi hạt tới vị trí tiếp theo. Do hạt tiếp theo là hạt bắt đầu nên ta kết thúc.- Do \(i = 3 > m\) nên chuỗi \(S\) có chứa chuỗi may mắn \(P\).
Bạn cần xác định chuỗi hạt cho trước có hợp phong thủy hay không?
Input
- Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10 ^ 4\)).
- Dòng tiếp theo chứa xâu \(S\) độ dài \(n\).
- Dòng tiếp theo chứa số nguyên \(m\) (\(1 \leq m \leq \min(n, 10 ^ 2)\)).
- Dòng tiếp theo chứa xâu \(P\) độ dài \(m\).
Output
- Nếu chuỗi hạt hợp phong thủy, in ra vị trí bắt đầu mà bạn chọn: \(j\) với \((1 \le j \le n)\) nghĩa là bạn bắt đầu từ vị trí \(j\) của chuỗi \(S\).
- Ngược lại, in ra số \(0\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \leq 10 ^ 2\).
- Subtask \(2\) (\(30\%\) số điểm): \(m \leq 3\).
- Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
3
dab
2
bd
Output
2
Comments
Nhận xét bài tập
Hiểu đề khó hơn thuật toán
dùng python độ phức tạp O(n.m) nhưng lại khó ac :((
This comment is hidden due to too much negative feedback. Click here to view it.
sao bài này em print(1) vẫn ac vậy ạ :v
bài này tớ sinh test hơi dễ nên các bạn cày trâu cũng AC, mất đi cái thú vị của bài.
các bài nộp trong contest vẫn được chấm với test dễ, các bài nộp luyện tập sẽ chấm với bộ test mới khó hơn