Gửi thư

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. Văn bản là một xâu \(S\) các chữ cái la tinh 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 \(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=truongngueNdu
         ngueNduquanNhat=Se

\(Sb = 'truongnguyendu '\)\(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.

Input

  • 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.

Output

  • Ghi ra độ dài của xâu \(S\) tìm được.

Example

Test 1

Input
truongnguyendu
nguyenduquannhat 
Output
22

Bình luận


  • -6
    hungeazyITistrue    3:48 p.m. 21 Tháng 6, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • 2
      MinhSharingan    10:05 p.m. 12 Tháng 3, 2021 chỉnh sửa 2

      program bt;
      const fi='';
      var
      s1,s2,tam:string;

      procedure xuli;
      var vt:byte;
      begin
      tam:=s1;
      while 1+1=2 do // lặp vô hạn cho đến khi vị trí bằng không hoặc tìm được vị trí để trừ
      begin
      vt:=pos(s2[1],tam);
      if vt<>0 then
      begin
      if pos(copy(tam,vt,length(tam)-vt+1),s2)=0 then
      delete(tam,vt,1)
      else
      begin
      writeln(length(s1)+length(s2)-length(copy(tam,vt,length(tam)-vt+1)));
      exit;
      end;
      end
      else
      begin
      writeln(length(s1)+length(s2));
      exit;
      end;
      end;
      end;

      begin
      readln(s1); readln(s2);
      xuli;

      end.


      • 11
        thich_viet_editor    8:40 p.m. 6 Tháng 8, 2020 chỉnh sửa 3

        HINT

        • Ý TƯỞNG: ta tạo ra một xâu \(T\) nhằm lưu lại xâu con của Sb từ vị trí \(i\) đến cuối xâu, sau đó ta sử dụng hàm find() để kiểm tra nếu vị trí đầu của xâu được tìm thấy nằm ở vị trí đầu của \(Se\)(vị trí 0) thì ta có kết quả là Se.size()+i;

        AC CODE

        int main()
        {
            cin>>Sb;
            cin>>Se;
            for(int i=0; i<=Sb.size(); i++)
            {
                string str = Sb.substr(i);//lấy xâu con từ vị trí i đến cuối xâu
                if (Se.find(str) == 0)
                    return cout << Se.size() + i, 0;//chiều dài của xâu Se cộng chiều dài xâu con trước vị trí i của xâu str
            }
        }