Editorial for PREFIX
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta sẽ chia bài toán làm hai trường hợp.
Trường hợp 1: ~|a| > |b|~, xâu ~a~ không phải tiền tố của xâu ~b~.
Trườnghợp2: ~|a|≤|b|~,ta sẽ tiến hành duyệt lần lượt từ ~1~ đến ~|a|~. Nếu ~∀i~, ~a_i = b_i\ (1≤i≤|a|)~ thì xâu ~a~ là tiền tố của xâu ~b~, ngược lại xâu ~a~ không phải là tiền tố của xâu ~b~.
Độ phức tạp ~O(|a|)~.
Comments