資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的 Z 演算法（線性時間模式搜尋演算法）
Z 演算法用於在字串中查詢模式的出現，時間複雜度為線性時間。假設字串長度為 n，要搜尋的模式大小為 m，則解決問題所需的時間複雜度為 O(m+n)。
Z 演算法使用 Z 陣列來查詢模式的出現。
Z 陣列
它是一個與字串長度相同的陣列。Z 陣列的每個元素包含從 I 開始的字串的最長子字串的長度，該子字串可以用作字串本身的字首。
演算法
在這個演算法中，我們給定一個長度為 n 的字串 S 和一個長度為 m 的要搜尋的模式 p。
我們將建立一個 Z 陣列。現在，演算法迴圈遍歷字串的所有字元，i 從 1 到 n-1。現在，我們將建立一個子字串 s[L-R]，它是一個字首子字串，使得 1 ≤ L ≤ I ≤ R。
現在，對於建立 i-1 的子字串 [L, R] 的正確區間和所有直到 i-1 的 z 值。使用以下步驟計算 z[i] 和新的區間 [L, R]：
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].
此過程在一次迭代中找到所有 Z 值（僅迴圈一次）。
示例
顯示演算法實現的程式：
#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;
}輸出
The patter ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46
更新於: 2020年4月17日
1K+ 次瀏覽
廣告