Z演算法

上一頁
下一頁

用於模式匹配的Z演算法

Z演算法是一種線性時間字串匹配演算法，用於在字串中搜索給定模式。其目的是搜尋字串中給定模式的所有出現。Z演算法依賴於Z陣列來查詢模式出現。Z陣列是一個整數陣列，儲存模式與文字任何子字串之間最長公共字首的長度。它與字串的長度相同。

Z演算法如何工作？

Z演算法透過構建一個名為Z陣列的輔助陣列來工作，該陣列儲存給定文字與文字任何子字串之間最長公共字首的長度。此陣列中的每個索引都儲存匹配字元的數量，從第0個索引到當前索引。

Z演算法需要以下步驟：

  • 首先，將模式和給定字串合併在一起。我們還需要在兩者之間新增一個特殊字元，該字元不在任何指定的字串中。假設我們使用美元符號（$）作為特殊字元。

  • 然後，為這個新建立的字串構建Z陣列。

  • 現在，檢查Z陣列的每個索引以查詢其值是否與正在搜尋的模式的長度匹配。如果值和長度匹配，則將模式標記為已找到。

  • 在最後一步中，從模式長度+1中減去索引號，這將導致模式的索引。

下圖說明了上述方法：

Z-Algorithm

讓我們瞭解輸入輸出場景：

Input:
Main String: "ABAAABCDBBABCDDEBCABC" 
Pattern: "ABC"
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

在上述場景中，我們正在主字串“ABAAABCDBBABCDDEBCABC”中查詢模式“ABC”。我們將檢查主字串中的每個位置並記下我們在哪裡找到匹配項。我們在位置4、10和18找到了模式“ABC”。

示例

以下是演示各種程式語言中Z演算法的示例：

C C++ Java Python
#include <stdio.h>
#include <string.h>
// function to fill Z array 
void fillZArray(const char* conStr, int zArr[]) {
   int n = strlen(conStr);
   int windLeft, windRight, k;
   // Initialize the window size to 0
   windLeft = windRight = 0; 
   // iterating over the characters of the new string
   for (int i = 1; i < n; i++) {
      // checking if current index is greater than right bound of window
      if (i > windRight) {
         // reset the window size to 0 and position it at the current index
         windLeft = windRight = i; 
         // extend right bound of window as long as characters match
         while (windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
             windRight++; 
         }
         // setting the Z value for the current index
         zArr[i] = windRight - windLeft;
         // decrementing right bound 
         windRight--;
      } else {
         // calculating corresponding index in window
         k = i - windLeft;
         // if Z value at corresponding index is less than remaining interval
         if (zArr[k] < windRight - i + 1) {
             zArr[i] = zArr[k]; 
         } else {
            // reset left bound of window to current index
            windLeft = i;
            // extend right bound of window as long as characters match
            while (windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
               windRight++;
            }
            // Setting the Z value for the current index
            zArr[i] = windRight - windLeft;
            // Decrement the right bound of the window
            windRight--;
         }
      }
   }
}
// function to implement the Z algorithm for pattern searching
void zAlgorithm(const char* mainString, const char* pattern, int array[], int *index) {
   // concatenate the pattern, a special character, and the main string
   char concatedStr[strlen(mainString) + strlen(pattern) + 1];
   strcpy(concatedStr, pattern);
   strcat(concatedStr, "$");
   strcat(concatedStr, mainString); 
   int patLen = strlen(pattern);
   int len = strlen(concatedStr);
   // Initialize the Z array
   int zArr[len];
   // Fill the Z array 
   fillZArray(concatedStr, zArr);
   // iterate over the Z array
   for (int i = 0; i < len; i++) {
      // if Z value equals length of the pattern, the pattern is found
      if (zArr[i] == patLen) {
         (*index)++;
         array[(*index)] = i - patLen - 1;
      }
   }
}
int main() {
   const char* mainString = "ABAAABCDBBABCDDEBCABC";
   const char* pattern = "ABC";
   // Initialize the location array and the index
   int locArray[strlen(mainString)];
   int index = -1;
   // Calling the Z algorithm function
   zAlgorithm(mainString, pattern, locArray, &index);
   // to print the result
   for (int i = 0; i <= index; i++) {
      printf("Pattern found at position: %d\n", locArray[i]);
   }
   return 0;
}

輸出

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

#include<iostream>
using namespace std;
// function to fill Z array 
void fillZArray(string conStr, int zArr[]) {
   int n = conStr.size();
   int windLeft, windRight, k;
   // initially window size is 0
   windLeft = windRight = 0;    
   // iterating over the characters of the new string
   for(int i = 1; i < n; i++) {
      // checking if current index is greater than right bound of window
      if(i > windRight) {
	     // reset the window size to 0 and position it at the current index
         windLeft = windRight = i; 
		 // extend right bound of window as long as characters match	
         while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
            windRight++;    
         }
		 // setting the Z value for the current index
         zArr[i] = windRight-windLeft;
		 // decrementing right bound 
         windRight--;
      }else {
	     // calculating corresponding index in window
         k = i-windLeft;
		 // if Z value at corresponding index is less than remaining interval
         if(zArr[k] < windRight-i+1)
            zArr[i] = zArr[k];    
         else {
		    // reset left bound of window to current index
            windLeft = i;
			// extend right bound of window as long as characters match
            while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
               windRight++;
            }
			// Setting the Z value for the current index
            zArr[i] = windRight - windLeft;
			// Decrement the right bound of the window
            windRight--;
         }
      }
   }
}
// function to implement the Z algorithm for pattern searching
void zAlgorithm(string mainString, string pattern, int array[], int *index) {
   // concatenate the pattern, a special character, and the main string
   string concatedStr = pattern + "$" + mainString;    
   int patLen = pattern.size();
   int len = concatedStr.size();
   // Initialize the Z array
   int zArr[len];
   // Fill the Z array 
   fillZArray(concatedStr, zArr);
   // iterate over the Z array
   for(int i = 0; i<len; i++) {
       // if Z value equals length of the pattern, the pattern is found
      if(zArr[i] == patLen) {
         (*index)++;
         array[(*index)] = i - patLen -1;
      }
   }
}
int main() {
   string mainString = "ABAAABCDBBABCDDEBCABC";
   string pattern = "ABC";
   // Initialize the location array and the index
   int locArray[mainString.size()];
   int index = -1;
   // Calling the Z algorithm function
   zAlgorithm(mainString, pattern, locArray, &index);
   // to print the result
   for(int i = 0; i <= index; i++) {
      cout << "Pattern found at position: " << locArray[i]<<endl;
   }
}

輸出

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

public class ZAlgorithm {
   // method to fill Z array    
   public static void fillZArray(String conStr, int[] zArr) {
      int n = conStr.length();
      int windLeft, windRight, k;
      // initially window size is 0
      windLeft = windRight = 0; 
      // iterating over the characters of the new string
      for (int i = 1; i < n; i++) {
         // checking if current index is greater than right bound of window
         if (i > windRight) {
            // reset the window size to 0 and position it at the current index
            windLeft = windRight = i;
            while (windRight < n && conStr.charAt(windRight - windLeft) == conStr.charAt(windRight)) {
               windRight++; 
            }
            // setting the Z value for the current index
            zArr[i] = windRight - windLeft;
            windRight--;
         } else {
            k = i - windLeft;
            if (zArr[k] < windRight - i + 1)
               zArr[i] = zArr[k]; 
            else {
               windLeft = i;
               while (windRight < n && conStr.charAt(windRight - windLeft) == conStr.charAt(windRight)) {
                  windRight++;
               }
               zArr[i] = windRight - windLeft;
               windRight--;
            }
         }
      }
   }
   // method to implement the Z algorithm for pattern searching
   public static void zAlgorithm(String mainString, String pattern, int[] array) {
      // concatenate the pattern, a special character, and the main string
      String concatedStr = pattern + "$" + mainString; 
      int patLen = pattern.length();
      int len = concatedStr.length();
      // Initialize the Z array
      int[] zArr = new int[len];
      // Fill the Z array 
      fillZArray(concatedStr, zArr);
      int index = -1;
      // iterate over the Z array
      for (int i = 0; i < len; i++) {
         // if Z value equals length of the pattern, the pattern is found
         if (zArr[i] == patLen) {
            index++;
            array[index] = i - patLen - 1;
         }
      }
      // Print the results
      for (int i = 0; i <= index; i++) {
         System.out.println("Pattern found at position: " + array[i]);
      }
   }
   public static void main(String[] args) {
      String mainString = "ABAAABCDBBABCDDEBCABC";
      String pattern = "ABC";
      // Initialize the location array and the index
      int[] locArray = new int[mainString.length()];
      // Calling the Z algorithm method
      zAlgorithm(mainString, pattern, locArray);
   }
}

輸出

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

# function to fill Z array 
def fillZArray(conStr, zArr):
    n = len(conStr)
    windLeft, windRight, k = 0, 0, 0  
    # iterating over the characters of the new string
    for i in range(1, n):
        if i > windRight:
            windLeft, windRight = i, i  
            while windRight < n and conStr[windRight - windLeft] == conStr[windRight]:
                windRight += 1  
            zArr[i] = windRight - windLeft
            windRight -= 1
        else:
            k = i - windLeft
            if zArr[k] < windRight - i + 1:
                zArr[i] = zArr[k] 
            else:
                windLeft = i
                while windRight < n and conStr[windRight - windLeft] == conStr[windRight]:
                    windRight += 1
                zArr[i] = windRight - windLeft
                windRight -= 1
# function to implement the Z algorithm for pattern searching
def zAlgorithm(mainString, pattern, array):
    concatedStr = pattern + "$" + mainString  
    patLen = len(pattern)
    length = len(concatedStr)
    zArr = [0] * length
    fillZArray(concatedStr, zArr)
    index = -1
    for i in range(length):
        if zArr[i] == patLen:
            index += 1
            array[index] = i - patLen - 1
    return index, array
def main():
    mainString = "ABAAABCDBBABCDDEBCABC"
    pattern = "ABC"
    locArray = [0] * len(mainString)
    index, locArray = zAlgorithm(mainString, pattern, locArray)
    for i in range(index + 1):
        print("Pattern found at position:", locArray[i])
if __name__ == "__main__":
    main()

輸出

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Z演算法的複雜度

Z演算法用於模式搜尋，其執行時間為線性時間。因此，其時間複雜度為O(m + n)，其中n是被搜尋字串的長度，m是被搜尋模式的長度。

列印頁面
上一頁
下一頁
廣告