Gửi thư

Tác giả:

Dạng bài

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

Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. Văn bản là một xâu \(S\) các chữ cái la tinh in thường. Để bảo mật nội dung văn bản, ông Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu \(Sb\) của xâu \(S\), bức thư thứ 2 là phần cuối \(Se\) của \(S\). Hai bức thư \(Sb\) và \(Se\) đảm bảo đầy đủ nội dung của \(S\), tuy nhiên có thể một phần cuối của \(Sb\) có thể được viết lặp lại trong phần đầu của \(Se\), song số kí tự được viết lặp lạ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 '\) và \(Se='nguyenduquannhat'\)
Yêu cầu: Cho hai xâu \(Sb\) và \(Se\), hãy xác định một xâu \(S\) có thể là nội dung của bức thư sao cho độ dài của xâu \(S\) là ngắn nhất.

Input

Dòng đầu chứa xâu \(Sb\),
Dòng thứ hai chứa xâu \(Se\).
Mỗi xâu có độ dài không quá 250.

Output

Ghi ra độ dài của xâu \(S\) tìm được.

Example

Test 1

Input

truongnguyendu
nguyenduquannhat

Output

Bình luận

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 } }

2 bình luận nữa