数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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算法在内存和时间方面效率更高。此外，它将模式的两个字符与字符串进行比较，通过减少比较次数来提高算法的性能。
149 次浏览
