Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau
Lấy l=0 nếu x là một tập của cùng một ký tự và l được tính bằng vị trí của ký tự
đầu tiên khác x[0] trong các trường hợp khác.
Trong suốt thuật toán xét 3 trường hợp:
-Vị trí xét nằm trong khoảng y[j..j+m-1]
-0<=k<=l và x[0..k-1]=y[j..j+k-1]
-l<=i<m và x[l..i-1]=y[j+l..i+j-l]
Khởi tạo (l,0,0)
Với mỗi attempt xét bộ ba (i,j,k)
Việc xét bộ tiếp theo dựa vào vị trí của i
-i=l
o nếu x[i]=y[i+j] bộ tiếp theo (i+1,j,k)
o nếu x[i]<>y[i+j] bộ tiếp theo (l,j+1,max(0,k-1))
-l<i<m
o nếu x[i]=y[i+j] bộ tiếp theo (i+1,j,k)
o nếu x[i]<>y[i+j] thì có 2 trường hợp được xét đến dựa vào kmpNext
·kmpNext[i]<l : (l,i+j-kmpNext[i],max(0,kmpNext[i]))
·kmpNext[i]>l : (kmpNext[i],i+j-kmpNext[i],l)
-i=m
o k<l và x[k]=y[j+k]: (I,j,k+1)
o Nếu một trong hai trường hợp k<l và x[k]<>y[j+k] hoặc k=l. Nếu k=l
thì thông báo một xuất hiện của x. Trong cả 2 trường hợp bộ tiếp
theo được tính toán giống như trường hợp l<i<m
Đặc điểm
-Có pha tiền xử lý với độ phức tạp O(m)
-Độ phức tạp thuật toán là O(n)
Thuật toán PreKmp: //thực hiện bước tiền xử lý
Input:
-Xâu mẫu X =(x0, x1,..,xm), độ dài m.
-Văn bản Y =(y0, y1,..,xn), độ dài n.
Output:
-Mọi vị trí xuất hiện của X trong Y.
Formats: AXAMAC(X, m, Y, n);
Actions:
Bước 1( Tiền xử lý):
int i,j,k,ell;
preKmp(x, m, kmpNext); //Tiền xử lý với độ phức tạp O(m)
for(ell=1;x[ell-1]==x[ell];ell++);
if(ell==m) ell=0;
i=ell;
j=k=0;
30
Bước 2 (Lặp)
while(j<=n-m){
while(i<m && x[i]==y[i+j]) i++;
if(i >=m){
while(k<ell && x[k]==y[j+k])k++;
if(k>=ell)OUTPUT (j);
}
j=j+(i-kmpNext[i-1]);
if(i==ell) k=Max(0, k-1);
else if(kmpNext[i-1]<=ell){
k=Max(0, kmpNext[i-1]);
i=ell;
}else{
k=ell;
i=kmpNext[i-1];
}
}
EndActions.
