Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới đối tác của mình. Văn bản là một xâu S các chữ cái Latinh in thường. Để bảo mật nội dung văn bản, ông Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu Sb của xâu S, bức thư thứ 2 là phần cuối Se của xâu S. Hai bức thư Sb và Se đảm bảo đầy đủ nội dung của S, tuy nhiên có thể một phần cuối của Sb có thể được viết lặp lại trong phần đầu của Se, song số kí tự được viết lặp lại không biết trước.
Ví
dụ: với văn bản S= ‘truongnguyenduquannhat’ tạo ra hai bức thư:
Sb=
‘truongnguyendu’ và Se= ‘nguyenduquannhat’
Yêu cầu: Cho hai xâu Sb và Se, hãy xác
định một xâu S có thể là nội dung của bức thư sao cho độ dài của xâu S là ngắn
nhất.
Dữ liệu: Dòng đầu chưa xâu Sb, dòng thứ
hai chứa xâu Se. Mỗi xâu có độ dài không quá 250.
Kết quả: Ghi ra độ dài của xâu S tìm được.
|
Dữ
liệu |
Kết
quả |
|
truongnguyendu nguyenduquannhat |
22 |
Ý tưởng:
-
Lần lượt xét các xâu con d, c tương ứng tính từ cuối xâu s1 và đầu xâu s2, nếu
d=c thì ta lưu lại độ dài của xâu d. Quá trình cứ tiếp tục và ta nhận được độ
dài xâu con chung dài nhất cần tìm (giả sử là Max).
uses crt;
var Sb,Se,d,c: string;
i,n,h,k,max: integer;
function min(a,b:integer): integer;
begin
if a > b then min:=a else min:=b;
end;
begin
clrscr;
readln(Sb);
read(Se);
i:=1; h:=length(sb);
k:=length(se); n:=min(h,k); max:=0;
while i<=n do
begin
d:=copy(sb,h-i+1,h);
c:=copy(se,1,i);
if d=c then max:=i;
inc(i);
end;
write(h+k-max);
readln;
end.
Đăng nhận xét