QBSTR spoj – Xâu con chung dài nhất

Nguồn đề bài http://vn.spoj.com/problems/QBSTR/

1. Đề bài QBSTR spoj

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.

Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

Input

Dòng 1: chứa xâu A

Dòng 2: chứa xâu B

Output

Chỉ gồm một dòng ghi độ dài xâu C tìm được

Example

Input:
abc1def2ghi3
abcdefghi123

Output:
10

2. Hướng dẫn QBSTR spoj

bài này phải sử dụng QHĐ.

+ Gọi F[i,j] là độ dài xâu con chung dài nhất tìm được khi xét i kí tự đầu tiên trong A và j kí tự đầu tiên trong B.

+ Nếu A[i]=B[j] thì F[i,j]:=F[i-1,j-1]+1.

+ ngược lại F[i,j]:=max(F[i-1,j],F[i,j-1]).

3. code tham khảo QBSTR spoj

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *