Rất thích tìm hiểu nên Bình thường xuyên đọc các tạp chí khoa học. Trong tạp chí đưa ra một vấn đề như sau:

Xét xâu \(S\) độ dài không vượt quá \(10^{18}\) chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) được mã hóa thành xâu \(S_{E}\) (chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) và ký tự \(‘0’\) đến \(‘9’\)) như sau: Đi từ trái qua phải, mã hóa dãy các ký tự liên tiếp bằng nhau trong \(S\) thành ký tự đại diện và số lượng. Độ dài các xâu mã hóa không vượt quá \(1000\).

Ví dụ, xâu \(S = \ aaabbbbaaaaaaaaaaz\) thì \(S_{E} = \ a3b4a10z1\)

Yêu cầu giải quyết hai vấn đề sau:

1) Cho xâu \(X\) được mã hóa thành \(X_{E}\) và xâu \(Y\) được mã hóa thành \(Y_{E}\), hãy tìm xâu \(Z\) là xâu con chung dài nhất của \(X\) và \(Y\). Đưa ra độ dài của xâu \(Z\).

• Ví dụ: \(X_{E}\ = \ a1b10\), \(Y_{E}\ = \ b3c9b4\) thì \(Z_{E}\ = \ b7\)

2) Cho xâu \(X\) được mã hóa thành \(X_{E}\), xâu \(Y\) được mã hóa thành \(Y_{E}\), tìm xâu \(W\) là xâu con chung liên tiếp dài nhất của cả \(X\) và \(Y\). Đưa ra độ dài của xâu \(W\).

• Ví dụ: \(X_{E}\ = \ a10b2c3\), \(Y_{E}\ = \ a5b2c10\) thì \(W_{E}\ = \ a5b2c3\)

Bình không biết giải quyết vấn đề này như thế nào. Bạn hãy giúp Bình nhé.

Dữ liệu vào:

+ Dòng 1: chứa xâu \(X_{E}\) là mã hóa của \(X\);

+ Dòng 2: chứa xâu \(Y_{E}\) là mã hóa của \(Y\).

Kết quả:

+ Dòng 1: ghi độ dài xâu con chung dài nhất của \(X\) và \(Y\);

+ Dòng 2: ghi độ dài xâu con chung liên tiếp dài nhất của \(X\) và \(Y\).

Ví dụ: