Thuật toán Z được sử dụng để tìm sự xuất hiện của một mẫu trong một chuỗi theo thời gian tuyến tính. Giả sử nếu độ dài của chuỗi là n và kích thước của mẫu cần tìm là m thì thời gian cần giải quyết sẽ có thứ tự là O (m + n) .
Thuật toán z sử dụng mảng Z để tìm sự xuất hiện của một mẫu.
Mảng Z
Nó là một mảng có cùng độ dài với chuỗi. Mỗi phần tử của mảng z bao gồm độ dài của chuỗi con dài nhất của chuỗi bắt đầu từ I, có thể được sử dụng làm tiền tố của chính chuỗi đó.
Thuật toán
Trong thuật toán này, chúng ta được cung cấp một chuỗi S có độ dài n và mẫu cần tìm p có độ dài m.
Chúng ta sẽ tạo một mảng z. Bây giờ, thuật toán lặp lại tất cả các ký tự của chuỗi với i =1 đến n-1. Bây giờ, chúng ta sẽ tạo một chuỗi con s [L-R] là một chuỗi con tiền tố sao cho 1 ≤ L ≤ I ≤ R.
Bây giờ, cho một khoảng thời gian chính xác để tạo chuỗi con [L, R] cho i-1 và tất cả các giá trị z lên đến i-1. Tính z [i] và khoảng mới [L, R] bằng các bước sau -
Step1: if i > R, no larger prefix-substring is possible. So, we will compute new interval bt comparing S[0] to S[i] i.e. string starting from index 0 i.e. from start with substring starting from index i. And find z[i] using z[i] = R - L + 1. Step 2: Else if, i ≤ R, [L, R] can be extended to i. For k = i-L, z[i] ≥ min(Z[k], R-i+1). Step 2.1: If, Z[k] < R-i+1, no longer prefix substring s[i] exist. Step 2.2: If Z[k] ≥ R-i+1, then there can be a longer substring. So, we will update [L, R] by changing L = i and changing R by matching from S[R+1].
Quá trình này tìm tất cả các giá trị Z trong một lần lặp duy nhất (chỉ lặp lại một lần).
Ví dụ
Chương trình hiển thị việc triển khai thuật toán -
#include<iostream>
using namespace std;
void createZarray(string str, int Z[]){
int n = str.length();
int L, R, k;
L = R = 0;
for (int i = 1; i < n; ++i){
if (i > R){
L = R = i;
while (R<n && str[R-L] == str[R])
R++;
Z[i] = R-L;
R--;
} else {
k = i-L;
if (Z[k] < R-i+1)
Z[i] = Z[k];
else {
L = i;
while (R<n && str[R-L] == str[R])
R++;
Z[i] = R-L;
R--;
}
}
}
}
void zAlgorithm(string text, string pattern){
string str = pattern+"$"+text;
int len = str.length();
int Z[len];
createZarray(str, Z);
for (int i = 0; i < len; ++i){
if (Z[i] == pattern.length())
cout<<(i-pattern.length()-1)<<"\t";
}
}
int main(){
string str = "Hello! Welcome To tutorials Point programming tutorial";
string pattern = "tutorial";
cout<<"The patter ' "<<pattern<<" ' is found in the string '"<<str<<" ' at index \t";
zAlgorithm(str, pattern);
return 0;
} Đầu ra
The patter ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46