Tiền tố dạng dãy con (Prefiquence)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai chuỗi nhị phân $a$ và $b$.

Chuỗi nhị phân là chuỗi chỉ gồm hai ký tự 0 và 1.

Với một số nguyên $k$ thỏa mãn $0 \le k \le n$, tiền tố có độ dài $k$ của chuỗi $a$ là chuỗi gồm $k$ ký tự đầu tiên của $a$:

$$a_1a_2\ldots a_k.$$

Khi $k=0$, tiền tố tương ứng là chuỗi rỗng.

Một chuỗi $x$ được gọi là dãy con của chuỗi $y$ nếu có thể thu được $x$ bằng cách xóa khỏi $y$ một số ký tự tùy ý, có thể không xóa ký tự nào hoặc xóa tất cả các ký tự, nhưng không được thay đổi thứ tự tương đối của các ký tự còn lại.

Ví dụ:

• 10 là một dãy con của 1110: có thể giữ lại một ký tự 1 đứng trước ký tự 0;
• 100 không phải là một dãy con của 1110, vì sau khi chọn một ký tự 1 không thể tìm được hai ký tự 0 phía sau theo đúng thứ tự;
• chuỗi rỗng luôn là dãy con của mọi chuỗi.

Nhiệm vụ của bạn là tìm giá trị lớn nhất của $k$ sao cho tiền tố gồm $k$ ký tự đầu tiên của chuỗi $a$ là một dãy con của chuỗi $b$.

Nói cách khác, cần tìm số lượng lớn nhất các ký tự liên tiếp tính từ đầu chuỗi $a$ có thể xuất hiện trong chuỗi $b$ đúng thứ tự, nhưng không nhất thiết phải nằm ở các vị trí liên tiếp trong $b$.

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ — lần lượt là độ dài của chuỗi $a$ và chuỗi $b$.

Dòng thứ hai chứa chuỗi nhị phân $a$ gồm đúng $n$ ký tự.

Dòng thứ ba chứa chuỗi nhị phân $b$ gồm đúng $m$ ký tự.

Output

In ra một số nguyên $k$ lớn nhất sao cho chuỗi:

$$a_1a_2\ldots a_k$$

là một dãy con của chuỗi $b$.

Nếu ngay cả ký tự đầu tiên của $a$ cũng không thể xuất hiện trong $b$ theo yêu cầu, đáp án bằng $0$.

Subtask

• Subtask 1 — 30% — Time Limit: 2.00 s: $1 \le n,m \le 2000$; $a$ và $b$ là các chuỗi nhị phân.
• Subtask 2 — 70% — Time Limit: 2.00 s: $1 \le n,m \le 2\cdot10^5$; $a$ và $b$ là các chuỗi nhị phân.

Ví dụ

Ví dụ 1

Input

5 4
10011
1110

Output

2

Giải thích

Chuỗi $a$ là:

10011.

Tiền tố có độ dài $2$ là:

10.

Chuỗi 10 là một dãy con của 1110: ta có thể chọn một ký tự 1 rồi chọn ký tự 0 ở cuối chuỗi.

Tuy nhiên, tiền tố có độ dài $3$ của $a$ là:

100.

Chuỗi 1110 chỉ có một ký tự 0, nên không thể chọn được hai ký tự 0 sau một ký tự 1 để tạo thành 100.

Vì vậy giá trị lớn nhất của $k$ là:

$$k=2.$$

Ví dụ 2

Input

3 3
100
110

Output

2

Giải thích

Tiền tố có độ dài $2$ của $a$ là 10.

Trong chuỗi 110, có thể chọn một ký tự 1 ở phía trước và ký tự 0 ở cuối để thu được 10.

Nếu xét tiền tố có độ dài $3$ là 100, chuỗi $b$ không có đủ hai ký tự 0.

Do đó đáp án là $2$.

Ví dụ 3

Input

1 3
1
111

Output

1

Giải thích

Chuỗi $a$ chỉ có một ký tự 1.

Chuỗi $b$ chứa ký tự 1, nên toàn bộ chuỗi $a$ là một dãy con của $b$.

Do đó:

$$k=1.$$

Ví dụ 4

Input

4 4
1011
1111

Output

1

Giải thích

Ký tự đầu tiên của $a$ là 1, và 1 xuất hiện trong $b$, nên tiền tố có độ dài $1$ là một dãy con của $b$.

Tiền tố có độ dài $2$ là:

10.

Chuỗi $b=$ 1111 không chứa ký tự 0, nên 10 không thể là một dãy con của $b$.

Vì vậy đáp án là $1$.

Ví dụ 5

Input

3 5
100
11010

Output

3

Giải thích

Toàn bộ chuỗi $a$ là:

100.

Trong chuỗi $b=$ 11010, ta có thể chọn lần lượt:

• một ký tự 1;
• một ký tự 0 đứng sau nó;
• một ký tự 0 khác đứng sau nữa.

Các ký tự được chọn theo đúng thứ tự tạo thành 100.

Do đó toàn bộ chuỗi $a$ là một dãy con của $b$ và:

$$k=3.$$

Ví dụ 6

Input

3 1
100
0

Output

0

Giải thích

Ký tự đầu tiên của $a$ là 1, trong khi chuỗi $b$ chỉ gồm ký tự 0.

Do đó ngay cả tiền tố có độ dài $1$ của $a$ cũng không phải là dãy con của $b$.

Tiền tố dài nhất thỏa mãn yêu cầu là chuỗi rỗng, có độ dài $0$.

Vì vậy đáp án là:

$$k=0.$$