Vấn đề: Tìm kiếm chuỗi

Bài toán: Cho chuỗi A có ðộ dài m, một chuỗi X có ðộ dài n. Kiểm tra xem chuỗi X xuất hiện trong chuỗi A tại các vị trí nào.

Cách thứ nhất: Duyệt mọi vị trí i của chuỗi A, với mỗi vị trí kiểm tra chuỗi X có xuất hiện ở vị trí này hay không. Thuật giải có ðộ phức tạp O(m*n). Một thuật giải tốt hơn chỉ mất O(m+n)


Cách thứ hai: Thuật toán Knuth-Morris-Pratt (KMP).

Thuật toán dựa vào một cách kiểm tra khá trực quan như sau: Ta cố ðịnh chuỗi A và di chuyển chuỗi X trượt theo chuỗi A. Giả sử chuỗi X ðang ở vị trí i so với chuỗi A. xét lần lượt các kí tự X1,X2…Xn  với các kí tự tương ứng của chuỗi A: Ai,Ai+1…Ai+n-1. Giả sử sự khác nhau ðầu tiên xuất hiện ở vị trí Xj  <>Ai+j-1. Gọi X1…j-1  = u = Ai…i+j-2  Lúc này ta sẽ dịch chuyển chuỗi X một ðọan ngắn nhất thỏa mãn:

-     Phần ðầu của chuỗi X trùng với phần cuối của Ai…i+j-2. Sau khi dịch chuyển , vị trí so sánh tương ứng với Ai+j-1 là Xj’. Ta có X1..j’-1 trùng với phần cuối của Ai…i+j-2 mà Ai…i+j-2 = X1…j-1 cho nên X1..j’-1 trùng với phần cuối của X1…j-1.

-     Xj<>Xj’

Do ðó nếu xét ðến vị trí j mà Xj <>Ai+j-1thì ta cần quan tâm ðến vị trí j’ thỏa mãn X1..j’-1

dài nhất trùng với phần cuối của X1…j-1 và Xj<>Xj’. Sử dụng Next[j] có ý nghĩa Next[j] = j’ nếu:

-     X1..j’-1 dài nhất trùng với phần cuối của X1…j-1

-     Xj<>Xj’

Mảng Next[j] có thể khởi tạo bằng Quy hoạch ðộng.

Mô tả thuật toán:

procedure Init;
var
j, jj: integer;
begin
j := 1;
jj := 0; Next[1] := 0;
while (j <= n) do begin
while (jj > 0)and(X[j] <> X[jj]) do jj := Next[jj]; Inc(j);
Inc(jj);
if X[j] = X[jj] then Next[j] := Next[jj] else Next[j] := jj;
end;
end;

procedure Process;
var
i, j: integer; Begin
Init
i := 1; j := 1; repeat
while (j > 0)and(X[j] <> A[i]) do j := Next[j]; Inc(i);
Inc(j);
if j > n then begin
Writeln(‘ xuat hien tai ‘,i - j + 1);
j := Next[j];
end;
until i>m; End;

  Bài toán áp dụng:

Cho xâu A và xâu B chỉ gồm các chữ cái thường. Xâu B ðược gọi là xuất hiện tại vị trí i của xâu A nếu: A[i] = B[1], A[i+1] = B[2], ..., A[i+length(B)-1] = B[length(B)].

Yêu cầu: Hãy tìm tất cả các vị trí mà B xuất hiện trong A.

Dữ liệu: SUBSTR.INP 
  Dòng 1: xâu A 
  Dòng 2: xâu B
  ðộ dài A, B không quá 1000000.

Kết quả: SUBSTR.OUT

   Ghi ra các vị trí tìm ðược trên 1 dòng (thứ tự tăng dần). Nếu B không xuất hiện trong A thì bỏ trắng.

 Ví dụ:
 Input:
 aaaaa
 aa
 Output:
 1 2 3 4