Java 实现Zhu-Takaoka字符串匹配算法

Zhu-Takaoka算法是一种最好的模式匹配算法之一。它是使用Boyer-Moore和KMP字符串匹配算法的组合开发的。

Zhu-Takaoka算法利用好字符移位和坏字符移位技术来解决问题。

问题陈述 - 我们已经给出了两个字符串。我们需要实现Zhu-Takaoka算法来进行模式匹配。

示例示例

输入

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

输出

解释

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.

方法

在朱-高丘算法中，在对模式字符串进行预处理后，我们将准备一个ZTBC表。因此，我们可以知道我们应该移动模式多少个索引以获得下一个匹配。

让我们逐步了解朱-高丘算法的工作原理。

首先，我们创建一个26 x 26的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 - 在全局定义一个26 x 26的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");
      }
   }
}