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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 *