#484. SPLITSTR – Tách xâu

An có hai xâu gồm các kí tự Latin in thường và một số nguyên . An muốn chọn ra xâu con rời nhau khác rỗng gồm các kí tự liên tiếp trong xâu sao cho các xâu này cũng xuất hiện rời nhau trong xâu với cùng một thứ tự như trong xâu và tổng độ dài của xâu này là lớn nhất có thể. Cụ thể hơn, An muốn tìm xâu khác rỗng sao cho:

• Xâu có thể được biểu diễn bởi chuỗi ở đó là những xâu bất kì (có thể là xâu rỗng).
• Xâu có thể được biểu diễn bởi chuỗi ở đó là những xâu bất kì (có thể là xâu rỗng).
• đạt giá trị lớn nhất, ở đó là độ dài của xâu .

Bạn hãy giúp An tính toán tổng độ dài lớn nhất của xâu thỏa mãn yêu cầu bài toán.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ;
• Dòng thứ hai chứa xâu ;
• Dòng thứ ba chứa xâu .

Dữ liệu ra:

• Một số nguyên duy nhất là giá trị lớn nhất của |, nếu không tồn tại cách tách xâu thỏa mãn thì đưa ra .

Ví dụ:

Dữ liệu vào:

2
abc
ab

Dữ liệu ra:

2

Dữ liệu vào:

4
bbaaababb
abbbabbaaaba

Dữ liệu ra:

7

Dữ liệu vào:

3
abc
def

Dữ liệu ra:

-1

Giải thích:

• Trong test : xâu tách được là bb, a, aa, ba.
• bb|a|aa|ba|b|b
• a|bb|babb|a|aa|ba

Giới hạn:

• ; Các xâu khác rỗng và độ dài không quá .