Thuật toán Z (Z Algorithm) tìm mẫu

Giới thiệu

Thuật toán Z (Z Algorithm) dùng mảng Z để lưu độ dài xâu con dài nhất bắt đầu từ mỗi ký tự. Trước hết, nối mẫu (pattern) và văn bản (text) với ký tự đặc biệt không xuất hiện trong cả hai (ví dụ: P$T).

Độ phức tạp: O(m + n), với m là độ dài mẫu, n là độ dài văn bản.

Đầu vào và Đầu ra

Đầu vào: Văn bản: "ABAAABCDBBABCDDEBCABC", Mẫu: "ABC"
Đầu ra: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Thuật toán

fillZArray(conStr, ZArray)

Đầu vào: Xâu nối pattern + text, mảng Z để lưu chỉ số.

Đầu ra: Mảng Z đã điền.

Begin
  n := độ dài conStr
  windLeft := 0 và windRight := 0
  với i := 1 đến n làm:
    nếu i > windRight thì
      windLeft := i và windRight := i
      trong khi windRight < n VÀ conStr[windRight-windLeft] = conStr[windRight] làm
        tăng windRight 1
      done
      ZArray[i] := windRight - windLeft
      giảm windRight 1
    ngược lại
      k := i - windLeft
      nếu ZArray[k] < windRight - i + 1 thì
        ZArray[i] := ZArray[k]
      ngược lại
        windLeft := i
        trong khi windRight < n VÀ conStr[windRight-windLeft] = conStr[windRight] làm
          tăng windRight 1
        done
        ZArray[i] := windRight - windLeft
        giảm windRight 1
      done
  done
End

zAlgorithm(text, pattern)

Đầu vào: Văn bản chính và mẫu cần tìm

Đầu ra: Vị trí tìm thấy mẫu

Begin
  conStr = nối pattern + "$" + text
  patLen := độ dài pattern
  len := độ dài conStr
  fillZArray(conStr, ZArray)
  với i := 0 đến len - 1 làm:
    nếu ZArray[i] = patLen thì
      in vị trí i - patLen - 1
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void fillZArray(string conStr, int zArr[]) {
  int n = conStr.size();
  int windLeft, windRight, k;
  windLeft = windRight = 0;
  for(int i = 1; i < n; i++) {
    if(i > windRight) {
      windLeft = windRight = i;
      while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
        windRight++;
      }
      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[windRight - windLeft] == conStr[windRight]) {
          windRight++;
        }
        zArr[i] = windRight - windLeft;
        windRight--;
      }
    }
  }
}

void zAlgorithm(string mainString, string pattern, int array[], int *index) {
  string concatedStr = pattern + "$" + mainString;
  int patLen = pattern.size();
  int len = concatedStr.size();
  int zArr[len];
  fillZArray(concatedStr, zArr);
  for(int i = 0; i < len; i++) {
    if(zArr[i] == patLen) {
      (*index)++;
      array[(*index)] = i - patLen - 1;
    }
  }
}

int main() {
  string mainString = "ABAAABCDBBABCDDEBCABC";
  string pattern = "ABC";
  int locArray[mainString.size()];
  int index = -1;
  zAlgorithm(mainString, pattern, locArray, &index);
  for(int i = 0; i <= index; i++) {
    cout << "Pattern found at position: " << locArray[i] << endl;
  }
}

Kết quả đầu ra

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