http://www.spoj.pl/problems/PSTRING/
Mọi người giải quyết bài này thế nào? Các cao thủ ra tay dùm cái

Bài này mình nghĩ là qhd O(length(x) * length(y)).
Gọi f[i, j] là số kí tự bỏ đi ít nhất từ xâu x[1..i] để xâu còn lại không nhận xâu y[1..j] làm xâu con.
Nếu nhiều test chắc vẫn không qua dc.

Bạn có thể nói rõ hơn về công thức được không? Mình chưa nghĩ ra.

Theo mình nghĩ qua thì là thế này:
f[i, j]: là số kí tự ít nhất bỏ đi từ i kí tự đầu tiên trong xâu X để xâu còn lại không chứa xâu Y và có đúng j kí tự cuối cùng trùng với j kí tự đầu tiên của xâu Y.

* Khởi tạo: f[i][j] = oo với mọi i, j. f[0, 0] = 0;

* QHD: for i: 0 -> length(x) - 1
for j: 0-> length(y) - 1
begin
// ko sử dụng kí tự x[i + 1]
f[i + 1, j] := min(f[i + 1, j], f[i, j] + 1);
// có sử dụng kí tự x[i + 1]
j + x[i + 1] -> j2 (biến đổi bằng kmp qhd từ trước)
if j2 < length(y) then f[i + 1, j2] := min(f[i + 1, j2], f[i, j]);
end;

* Lấy kết quả: res := min (f[length(x), j]) với 0 <= j <= length(y) - 1

* Độ phức tạp: O(length(x) * length(y)). Mình nghĩ là có vài test thì cũgn vẫn chạy được trong thời gian 3s vì thuật toán khá đơn giản, ít phép tính toán. Phần qhd kmp chuẩn bị sẵn chạy cũng nhanh vì chỉ có độ phức tạp O(length(y)).

Lúc Trước mình tưởng xâu con có thể không liên tiếp . Tại đề bài không nói rõ, xem lại test ví dụ mới biết. Trong trường hợp xâu con liên tiếp thì cũng phức tạp hơn một chút. Mình cũng làm như lightning31.

Ừ mình cũng nhầm sang xâu con không liên tiếp. Mọi người thử nghĩ xem liệu có thể giải bài này với xâu con không liên tiếp với độ phức tạp đa thức được hay không?

Nếu là không liên tiếp thì bài toán sẽ dễ hơn. Không cần sử dụng kmp, qhđ với trạng thái như mình nói ở trên.