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