Chuỗi hạt nhiều màu

View as PDF




Author:
Problem types
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\)\(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\)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\)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


  • 0
    penistone    2:26 p.m. 27 sep, 2024

    Nhận xét bài tập

    Hiểu đề khó hơn thuật toán


    • 0
      blinh    8:16 p.m. 1 may, 2024

      dùng python độ phức tạp O(n.m) nhưng lại khó ac :((


      • -15
        medusa    2:23 p.m. 12 sep, 2022

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 0
          hivong    1:14 p.m. 12 sep, 2022

          sao bài này em print(1) vẫn ac vậy ạ :v

          1 reply

          • 0
            letangphuquy    10:04 p.m. 10 sep, 2022

            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

            1 reply