Tóm tắt: đây là bài toán tìm xâu con (substring) trên xâu vòng tròn.

Lưu ý: ở đây tôi dùng từ "substring" có nghĩa là xâu con không liên tiếp chứ không phải là xâu liên tiếp như bạn thường thấy.

Vì mình muốn phát biểu của đề bài dễ hiểu nên đã mô tả thuật toán cày trâu của subtask1, các bạn chỉ việc dịch từ lời nói thành code.

Subtask 1: \(n \le 100\)

Ta sẽ chọn từng vị trí bắt đầu rồi tiến hành tìm substring như đề bài bảo.

Độ phức tạp \(O(n^2)\)

Subtask 2: \(m \le 3\)

Với \(m = 2\), ta thấy chỉ cần 2 kí tự có xuất hiện trong xâu thì ta sẽ tìm được.
Cụ thể, giả sử \(P =\) ab, nếu trong xâu \(S\):

• a xuất hiện trước b \(\rightarrow\) in ra \(1\)
• a xuất hiện sau b \(\rightarrow\) in ra vị trí của b.

Với \(m = 3\), giả sử $P = $ abc. Kí hiệu \(xa, xb, xc\) là vị trí xuất hiện các kí tự a, b, c. Nếu \(S\) có chứa \(P\) thì:

• \(xa < xb < xc\) hoặc
• \(xc < xa < xb\) hoặc
• \(xb < xc < xa\)

Nhận thấy những điều kiện trên sẽ tương tự với việc tìm các xâu abc, cab, bca trong xâu \(S\).

Công việc của ta chỉ là tìm substring trên xâu bình thường (không vòng tròn) nhưng sẽ xét 3 trường hợp của \(P\). Đáp án sẽ là \(xa\).

Độ phức tạp \(O(n)\)

Subtask 3: \(m \le n\)

Tổng quát hóa ý tưởng của subtask 2: thay vì đẩy xâu \(S\) theo vòng tròn, ta sẽ đẩy xâu \(P\) theo vòng tròn và tiến hành tìm substring.

Trong quá trình tìm, phải ghi nhớ chỉ số của kí tự đầu tiên của \(P\) là bao nhiêu? Đó là vì khi ta đẩy xâu \(P\) thì các kí tự cũng bị thay đổi vị trí.
Ví dụ: Sau khi đẩy về "bên phải" một lần thì kí tự đầu tiên trong xâu \(P\) ban đầu là kí tự thứ hai trong xâu \(P\) hiện tại (sau khi đẩy).

Trong lúc tìm \(P\) trong \(S\), nhớ ghi nhận lại vị trí mà ta tìm thấy kí tự đầu tiên đó - nó sẽ là đáp án bài toán (vì \(m \le n\) nên tìm từ kí tự đầu tiên của \(P\) thì chắc chắn sẽ tìm thấy hết mọi kí tự của \(P\)).

Độ phức tạp \(O(nm)\)

Bonus:

• Có một điều kiện giúp thuật trâu chạy được trong \(0,1s\): chỉ bắt đầu tại những vị trí cùng màu với \(P[0]\)
• Vì sự cố nên bộ test trong contest rất dễ (chỉ cần in ra 1 hoặc cày trâu vẫn \(AC\))
• Cày trâu "ngây thơ" sẽ qua được trong \(1s\) nhưng không qua được \(0,1s\)
• Bộ test chưa có test giết "trâu khôn", sẽ add (soon^TM)