Java程式實現Zhu-Takaoka字串匹配演算法

---

Zhu-Takaoka演算法是用於模式匹配的最佳演算法之一。它結合了Boyer-Moore和KMP字串匹配演算法的優勢。

Zhu-Takaoka演算法利用良好的字元偏移和壞字元偏移技術來解決問題。

問題陳述 - 我們給定兩個字串。我們需要實現Zhu-Takaoka演算法進行模式匹配。

示例

輸入

str = "PQRDPQRSSE"; patt = "PQRS";

輸出

5

解釋

The ‘PQRS’ pattern exists at position 5. So, it prints 5.

輸入

str = "PQRDPQRSSE"; patt = "PRQS";

輸出

-1

解釋

The pattern doesn’t exist in the given string.

輸入

str = "WELWELWELCOME"; patt = "WEL";

輸出

1, 4, 7

解釋

The pattern exists at multiple positions in the given string.

方法

在Zhu-Takaoka演算法中，我們將在預處理模式字串後準備一個ZTBC表。這樣，我們就可以知道在發生任何不匹配時，應該將模式移動多少索引才能獲得下一個匹配。

讓我們逐步瞭解Zhu-Takaoka演算法的工作原理。

首先，我們建立一個26x26維度的ZTBC表。表的每一行和每一列都用大寫字母表示。

在第一階段，所有表元素都等於模式長度，假設在發生任何不匹配時我們需要傳遞整個模式。

因此，根據“PQRS”模式，表值如下所示。

A  B  C  D  E  F  …
A  4  4  4  4  4  4
B  4  4  4  4  4  4
C  4  4  4  4  4  4
D  4  4  4  4  4  4
..

在此演算法中，我們需要將模式的兩個字元與字串從右到左進行匹配。如果我們在模式中找到兩個連續匹配的元素，則需要移動模式，使其字元對在字串和模式中都匹配。

因此，相應地更新ZTBC表。

table [pattern[p-1]][pattern[p]] = len – p - 1 ;

預處理表後，我們需要開始比較字串和模式。

演算法

• 步驟1 - 在全域性範圍內定義26x26維度的ZTBCTable[]陣列，以儲存模式的預處理移動。

• 步驟2 - 執行prepareZTBCTable()以在預處理模式後填充ZTBCTable()陣列。

• 步驟2.1 - 在prepareZTBCTable()函式中，將所有陣列元素初始化為模式長度。

• 步驟2.2 - 將ZTBCTable[p][patt.charAt(0) - 'A']初始化為模式長度-1，表示單個字元匹配時的移動。

• 步驟2.3 - 將ZTBCTable[patt.charAt(p - 1) - 'A'][patt.charAt(p) - 'A']更新為模式長度-1-索引。

• 步驟3 - 接下來，將q初始化為0，並將isPatPresent初始化為false值。

• 步驟4 - 進行迭代，直到q小於字串和模式長度的差。

• 步驟5 - 進行巢狀迴圈迭代，直到字串和模式字元從最後開始匹配。

• 步驟6 - 如果p小於0，則表示我們找到了匹配。因此，列印q作為起始索引，並將isPatPresent更新為true。

• 步驟7 - 否則，將ZTBCTable[str.charAt(q + patt_len - 2) - 'A'][str.charAt(q + patt_len - 1) - 'A']新增到“q”變數以移動模式。

• 步驟8 - 最後，如果isPatPresent的值為false，則列印“模式不存在於字串中”。

示例

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {
   // Declaring custom strings as inputs and patterns
   public static String str = "PQRDPQRSSE";
   public static String patt = "PQRS";
   // And their lengths
   public static int str_len = str.length();
   public static int patt_len = patt.length();
   public static int[][] ZTBCTable = new int[26][26];
   public static void prepareZTBCTable() {
      int p, q;
      // Initialize the table
      for (p = 0; p < 26; ++p)
         for (q = 0; q < 26; ++q)
            ZTBCTable[p][q] = patt_len;
      for (p = 0; p < 26; ++p)
         ZTBCTable[p][patt.charAt(0) - 'A'] = patt_len - 1;
      for (p = 1; p < patt_len - 1; ++p)
         ZTBCTable[patt.charAt(p - 1) - 'A'][patt.charAt(p) - 'A'] = patt_len - 1 - p;
   }
   public static void main(String args[]) {
      int p, q;
      // Preparing a ZTBC table
      prepareZTBCTable();
      q = 0;
      boolean isPatPresent = false;
      while (q <= str_len - patt_len) {
         p = patt_len - 1;
         while (p >= 0 && patt.charAt(p) == str.charAt(p + q))
            --p;
         if (p < 0) {
            // When we get the pattern
            System.out.println("Pattern exists at index " + (q + 1));
            q += patt_len;
            isPatPresent = true;
         } else {
            // Move in the string
            q += ZTBCTable[str.charAt(q + patt_len - 2) - 'A'][str.charAt(q + patt_len - 1) - 'A'];
         }
      }
      if(!isPatPresent){
         System.out.println("Pattern doesn't exists in the given string");
      }
   }
} 

輸出

Pattern exists at index 5

時間複雜度 - O(N*M)，其中N是字串長度，M是模式長度。

空間複雜度 - O(26*26) 用於儲存模式移動。

Zhu-Takaoka演算法在記憶體和時間方面效率更高。此外，它將模式的兩個字元與字串進行比較，透過減少比較次數來提高演算法的效能。