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

javaobject oriented programmingprogramming更新于 2024/7/30 20:28:17

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

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

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

示例

输入

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

输出

5

解释

"PQRS"模式存在于位置 5。因此,它打印 5。

输入

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

输出

-1

解释

给定的字符串中不存在该模式。

输入

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

输出

1, 4, 7

解释

该模式存在于给定字符串的多个位置。

方法

在 Zhu-Takaoka 算法中,我们将在预处理模式字符串后准备一个 ZTBC 表。因此,我们可以知道应该移动多少个索引才能获得下一个匹配。

让我们逐步了解 Zhu-Takaoka 算法的工作原理。

首先,我们创建一个尺寸为 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 - 使用模式长度 - 1 初始化 ZTBCTable[p][patt.charAt(0) - 'A'],表示单个字符时的移动匹配。

  • 步骤 2.3 - 使用模式长度 – 1 – 索引更新 ZTBCTable[patt.charAt(p - 1) - 'A'][patt.charAt(p) - 'A']。

  • 步骤 3 - 接下来,用 0 初始化 q,用 false 值初始化 isPatPresent。

  • 步骤 4 - 进行迭代,直到 q 小于字符串和模式长度差。

  • 步骤 5 - 进行嵌套 loo 迭代,直到字符串和模式字符从最后一个匹配。

  • 步骤 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 {
    // 将自定义字符串声明为输入和模式
    public static String str = "PQRDPQRSSE";
    public static String patt = "PQRS";
    // 及其长度
    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;
      // 初始化表
      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;
      // 准备 ZTBC 表
      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) {
            // 当我们获得模式时
            System.out.println("Pattern exists at index " + (q + 1));
            q += patt_len;
            isPatPresent = true;
         } else {
            // 移动字符串
            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 算法在内存和时间方面更高效。此外,它将模式的两个字符与字符串进行比较,通过减少比较来提高算法的性能。


相关文章


有用资源