模式搜索算法有时也称为字符串搜索算法，并被视为字符串算法的一部分。这些算法在搜索另一个字符串中的字符串的情况下非常有用。
模式搜索算法的特点：
- 模式搜索算法应该快速准确地识别熟悉的模式。
- 识别并分类不熟悉的模式。
- 即使部分隐藏，也能识别模式。
- 轻松、自动地快速识别模式。
朴素模式搜索算法
朴素模式搜索是其他模式搜索算法中最简单的方法。它检查模式中主字符串的所有字符。该算法对于较小的文本很有帮助。它不需要任何预处理阶段。我们可以通过检查一次字符串来找到子字符串。它也不占用额外的空间来执行操作。
朴素模式搜索方法的时间复杂度为 O(m*n)。 m 是模式的大小，n 是主字符串的大小。
// Java program for Naive Pattern
// Searching algorithm
class GFG {
static void search(char[] pat, char[] txt)
{
int M = pat.length;
int N = txt.length;
/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++) {
int j;
/* For current index i, check for pattern match
*/
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
// if pat[0...M-1] = txt[i, i+1, ...i+M-1]
if (j == M)
System.out.println("Pattern found at index "
+ i);
}
}
// Driver's Code
public static void main(String[] args)
{
char txt[] = "AABAACAADAABAAABAA".toCharArray();
char pat[] = "AABA".toCharArray();
// Function call
search(pat, txt);
}
}
Python:
# Python program for above approach
def search(pat, txt):
M = len(pat)
N = len(txt)
for i in range(N-M):
for j in range(M):
k = j+1
if(txt[i+j] != pat[j]):
break
if(k == M):
print("Pattern found at index ", i)
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
|
Javascript:
// JS program for Naive Pattern
// Searching algorithm
function search(pat, txt)
{
let M = pat.length;
let N = txt.length;
/* A loop to slide pat[] one by one */
for (let i = 0; i <= N - M; i++) {
let j = 0;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
console.log("Pattern found at index",i);
}
}
// Driver's Code
let txt = "AABAACAADAABAAABAA";
let pat = "AABA";
// Function call
search(pat, txt);
|
KMP算法
KMP算法用于在“文本”中查找“模式”。该算法从左到右逐个字符进行比较。但每当发生不匹配时，它都会使用一个名为“前缀表”的预处理表来跳过匹配时的字符比较。有时前缀表也称为LPS表。这里 LPS 代表“最长的正确前缀，也是后缀”。
我们使用LPS表来决定当发生不匹配时要跳过多少个字符进行比较。当发生不匹配时，检查模式中不匹配字符的前一个字符的 LPS 值。如果为“0”，则开始将模式的第一个字符与下一个字符与文本中不匹配的字符进行比较。如果它不是“0”，则开始将索引值等于前一个字符的LPS值的字符与模式中的不匹配字符与文本中的不匹配字符进行比较。
// Java program for implementation of KMP pattern searching
// algorithm
public class KMP_String_Matching {
void KMPSearch(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
// create lps[] that will hold the longest prefix suffix
// values for pattern
int lps[] = new int[M];
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
}
if (j == M) {
System.out.println("Found pattern " + "at index " + (i - j));
j = lps[j - 1];
}
// j 个匹配后不匹配 ；
else if (i < N && pat.charAt(j) != txt.charAt(i)) {
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(String pat, int M, int lps[])
{
//上一个最长前缀后缀的长度 ；
int len = 0;
int i = 1;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0) {
len = lps[len - 1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = len;
i++;
}
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
String txt = "ABABDABACDABABCABAB";
String pat = "ABABCABAB";
new KMP_String_Matching().KMPSearch(pat, txt);
}
}
Python
# Python program for implementation of KMP pattern searching
# algorithm
def computeLPSArray(pat, M, lps):
len = 0 # length of the previous longest prefix suffix
lps[0] # lps[0] is always 0
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i] == pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while (N - i) >= (M - j):
if pat[j] == txt[i]:
j += 1
i += 1
if j == M:
print("Found pattern at index:", i-j)
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway
if j != 0:
j = lps[j-1]
else:
i += 1
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)
|
Javascript
// JS program for implementation of KMP pattern searching
// algorithm
// Prlets occurrences of txt[] in pat[]
function computeLPSArray(pat, M, lps)
{
// length of the previous longest prefix suffix
let len = 0;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
let i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0) {
len = lps[len - 1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
function KMPSearch(pat, txt) {
let M = pat.length;
let N = txt.length
// create lps[] that will hold the longest prefix suffix
// values for pattern
let lps = [];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
let i = 0; // index for txt[]
let j = 0; // index for pat[]
while ((N - i) >= (M - j)) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
console.log("Found pattern at index:", i - j);
j = lps[j - 1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
// Fills lps[] for given pattern pat[0..M-1]
// Driver program to test above function
let txt = "ABABDABACDABABCABAB";
let pat = "ABABCABAB";
KMPSearch(pat, txt);
|
拉宾卡普算法：
Rabin-Karp 算法是一种使用哈希函数在文本中搜索/匹配模式的算法。与 Naive 字符串匹配算法不同，它不会在初始阶段遍历每个字符，而是过滤不匹配的字符，然后执行比较。
Rabin-Karp 比较字符串的哈希值，而不是字符串本身。为了提高效率，可以根据当前位置的哈希值轻松计算出文本中下一个位置的哈希值。
Rabin-Karp 算法的工作原理
- 初步计算模式P的哈希值。
- 从字符串的开头开始迭代：
- 计算当前长度为m的子串的哈希值。
- 如果当前子串的哈希值与模式相同，则检查子字符串与模式是否相同。
- 如果它们相同，则将起始索引存储为有效答案。否则，继续处理下一个子字符串。
- 返回起始索引作为所需答案。
import java.io.*;
import java.lang.*;
import java.util.*;
/* pat -> pattern
txt -> text
q -> A prime number
*/
public class GFG {
// d is the number of characters in the input alphabet
public final static int d = 256;
public static void search(String pat, String txt, int q)
{
int M = pat.length();
int N = txt.length();
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
// The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
// 计算模式的哈希值和文本的第一个
//窗口的哈希值；
for (i = 0; i < M; i++) {
p = (d * p + pat.charAt(i)) % q;
t = (d * t + txt.charAt(i)) % q;
}
// Slide the pattern over text one by one
for (i = 0; i <= N - M; i++) {
//检查当前窗口中文本和模式的哈希值。如果哈希值匹配
//则只逐个检查字符 ；
if (p == t) {
/* Check for characters one by one */
for (j = 0; j < M; j++) {
if (txt.charAt(i + j)
!= pat.charAt(j)) {
break;
}
}
// if p == t and pat[0...M-1] = txt[i, i+1,
// ...i+M-1]
if (j == M) {
System.out.println(
"Pattern found at index " + i);
}
}
// 计算下一个文本窗口的哈希值：
// 删除前导数字，添加尾数 ；
if (i < N - M) {
t = (d * (t - txt.charAt(i) * h)
+ txt.charAt(i + M))
% q;
// We might get negative value of t,
// converting it to positive
if (t < 0)
t = (t + q);
}
}
}
/* Driver code */
public static void main(String[] args)
{
String txt = "GEEKS FOR GEEKS";
String pat = "GEEK";
// A prime number
int q = 101;
// Function Call
search(pat, txt, q);
}
}
|
时间复杂度：
- Rabin-Karp 算法的平均和最佳情况运行时间为 O(n+m)，但其最坏情况时间为 O(nm)。
- Rabin-Karp 算法的最坏情况发生在当模式和文本的所有字符都相同且 txt[] 的所有子字符串的哈希值与 pat[] 的哈希值匹配时。
空间复杂度：
Rabin-Karp 算法的空间复杂度为 O(1)，这意味着无论输入文本和模式的大小如何，所需的内存量都是恒定的。这是因为算法只需要存储一些随着算法处理文本和模式而更新的变量。具体来说，算法需要存储模式的哈希值、文本中当前窗口的哈希值以及一些循环计数器和临时变量。由于这些变量的大小是固定的，因此空间复杂度是恒定的。
Z算法：
该算法在线性时间内查找文本中所有出现的模式。设文本长度为n，模式长度为m，则总时间为O(m + n)，空间复杂度为线性。 Z 算法的工作原理是维护一个称为 Z 数组的辅助数组。该 Z 数组存储从当前索引开始的最长子字符串的长度，这也是它的前缀。
什么是 Z 数组？
对于字符串 str[0..n-1]，Z 数组与字符串长度相同。 Z数组的元素Z存储从str开始的最长子串的长度，也是str[0..n-1]的前缀。 Z 数组的第一个条目意义不大，因为完整的字符串始终是其自身的前缀。
例子：
索引 0 1 2 3 4 5 6 7 8 9 10 11
文本 a a b c a a b x a a a z
Z 值 X 1 0 0 3 1 0 0 2 2 1 0
如何构造Z数组？
一个简单的解决方案是运行两个嵌套循环，外部循环访问每个索引，内部循环查找与从当前索引开始的子字符串匹配的最长前缀的长度。该解法的时间复杂度为O(n2)。
我们可以在线性时间内构造 Z 数组。这个想法是维护一个区间 [L, R]，即具有最大 R 的区间，
使得 [L, R] 是前缀子串（子串也是前缀。
维持此间隔的步骤如下 –
- 如果i > R则不存在在 i 之前开始并在 i 之后结束的前缀子串，因此我们重置 L 和 R 并通过比较str[0..]与str[i.. ] 计算新的 [L, R]并得到Z (= R-L+1)。
- 如果i <= R则让K = iL，现在Z >= min(Z[K], R-i+1) 因为 str[i..] 与str[K..]匹配至少R- i+1 个字符（它们在 [L, R] 区间内，我们知道这是前缀子串）。 现在出现两种子情况：
- 如果Z[K] < R-i+1 则不存在从 str 开始的前缀子串（否则Z[K]会更大），因此 Z = Z[K] 且区间 [L, R]保持不变。
如果Z[K] >= R-i+1那么可以扩展 [L, R] 间隔，因此我们将 L 设置为 i 并从str[R]开始匹配并得到新的 R 然后我们将更新间隔[L, R] 并计算Z (=R-L+1)。
// A Java program that implements Z algorithm for pattern
// searching
import java.io.*;
class GFG
{
// prints all occurrences of pattern in text using Z
// algo
static void search(String text, String pattern)
{
// Create concatenated string "P$T"
String concat = pattern + "$" + text;
int l = concat.length();
// Construct Z array
int[] Z = new int[l];
getZarr(concat, Z);
// now looping through Z array for matching
// condition
for (int i = 0; i < l; i++) {
// if Z[i] (matched region) is equal to pattern
// length we got the pattern
if (Z[i] == pattern.length()) {
System.out.println(
"Pattern found at index "
+ (i - pattern.length() - 1));
}
}
}
// Fills Z array for given string str[]
static void getZarr(String str, int[] Z)
{
int n = str.length();
// [L, R] make a window which matches with prefix of
// s
int L = 0, R = 0, k;
for (int i = 1; i < n; ++i) {
// if i>R nothing matches so we will calculate.
// Z[i] using naive way.
if (i > R) {
L = R = i;
// 启动时 R-L = 0，因此将从第 0 个索引开始
// 从第 0 个索引开始检查。例如
// 对于字符串 "ababab "和 i = 1，R 的值仍为 0，Z[i] 变为 0。
// 字符串为 "ababab "且 i = 1 时，R 的值仍为 0，Z[i] 变为 0。
// "aaaaaa "且 i = 1 时，Z[i] 和 R 变为 5
while (R < n
&& str.charAt(R - L)
== str.charAt(R)) {
R++;
}
Z[i] = R - L;
R--;
}
else {
// k = i-L so k corresponds to number which
// matches in [L, R] interval.
k = i - L;
// 如果 Z[k] 小于剩余区间
// 则 Z[i] 等于 Z[k]。
// 例如，str = "ababab"，i = 3，R = 5
// 和 L = 2
if (Z[k] < R - i + 1)
Z[i] = Z[k];
// For example str = "aaaaaa" and i = 2, R
// is 5, L is 0
else {
// else start from R and check manually
L = i;
while (R < n
&& str.charAt(R - L)
== str.charAt(R)) {
R++;
}
Z[i] = R - L;
R--;
}
}
}
}
public static void main(String[] args)
{
String text = "GEEKS FOR GEEKS";
String pattern = "GEEK";
search(text, pattern);
}
}
// This code is contributed by lokeshmvs21.
|
Aho-Corasick 算法：
Aho-Corasick 算法在 O(n + m + z) 时间内查找所有单词，其中 z 是文本中单词出现的总数。 Aho-Corasick 字符串匹配算法构成了原始 Unix 命令“fgrep”的基础。
预处理：构建arr[]中所有单词的自动机，自动机主要有三个功能：
- Go To： 该函数简单地跟踪 arr[] 中所有单词的 Trie 边缘。 它表示为二维数组 g[][]，其中我们存储当前状态和字符的下一个状态。
- 失败：该函数存储当前字符在 Trie 中没有边时所遵循的所有边。它表示为一维数组 f[]，我们在其中存储当前状态的下一个状态。
- 输出：存储以当前状态结束的所有单词的索引。 它表示为一维数组 o[]，其中我们将所有匹配单词的索引存储为当前状态的位图。
// Java program for implementation of
// Aho Corasick algorithm for String
// matching
import java.util.*;
class GFG {
// 匹配器的最大状态数
// 机器的最大状态数。应等于
// 所有关键字长度之和。
static int MAXS = 500;
// Maximum number of characters
// in input alphabet
static int MAXC = 26;
// 使用 out[] 实现输出函数。
// 如果在机器输入时出现索引为 i 的单词，则该掩码中的第 i 位为 1。
// 如果机器进入
// 此状态。
static int[] out = new int[MAXS];
// FAILURE FUNCTION IS IMPLEMENTED USING f[]
static int[] f = new int[MAXS];
// GOTO FUNCTION (OR TRIE) IS
// IMPLEMENTED USING g[][]
static int[][] g = new int[MAXS][MAXC];
// Builds the String matching machine.
// arr - array of words. The index of each keyword is
// important:
// "out[state] & (1 << i)" is > 0 if we just
// found
// word[i] in the text.
// Returns the number of states that the built machine
// has. States are numbered 0 up to the return value -
// 1, inclusive.
static int buildMatchingMachine(String arr[], int k)
{
// Initialize all values in output function as 0.
Arrays.fill(out, 0);
// Initialize all values in goto function as -1.
for (int i = 0; i < MAXS; i++)
Arrays.fill(g[i], -1);
// Initially, we just have the 0 state
int states = 1;
// 对于所有在 Trie 中没有
// 在 Trie 中没有从根（或状态 0）开始的边、
// 为状态 0 本身添加一条 goto 边
for (int i = 0; i < k; ++i) {
String word = arr[i];
int currentState = 0;
// Insert all characters of current
// word in arr[]
for (int j = 0; j < word.length(); ++j) {
int ch = word.charAt(j) - 'a';
// Allocate a new node (create a new state)
// if a node for ch doesn't exist.
if (g[currentState][ch] == -1)
g[currentState][ch] = states++;
currentState = g[currentState][ch];
}
// Add current word in output function
out[currentState] |= (1 << i);
}
// For all characters which don't have
// an edge from root (or state 0) in Trie,
// add a goto edge to state 0 itself
for (int ch = 0; ch < MAXC; ++ch)
if (g[0][ch] == -1)
g[0][ch] = 0;
// Now, let's build the failure function
// Initialize values in fail function
Arrays.fill(f, -1);
// Failure function is computed in
// breadth first order
// using a queue
Queue<Integer> q = new LinkedList<>();
// Iterate over every possible input
for (int ch = 0; ch < MAXC; ++ch) {
// All nodes of depth 1 have failure
// function value as 0. For example,
// in above diagram we move to 0
// from states 1 and 3.
if (g[0][ch] != 0) {
f[g[0][ch]] = 0;
q.add(g[0][ch]);
}
}
// Now queue has states 1 and 3
while (!q.isEmpty()) {
// Remove the front state from queue
int state = q.peek();
q.remove();
// For the removed state, find failure
// function for all those characters
// for which goto function is
// not defined.
for (int ch = 0; ch < MAXC; ++ch) {
// If goto function is defined for
// character 'ch' and 'state'
if (g[state][ch] != -1) {
// Find failure state of removed state
int failure = f[state];
// Find the deepest node labeled by
// proper suffix of String from root to
// current state.
while (g[failure][ch] == -1)
failure = f[failure];
failure = g[failure][ch];
f[g[state][ch]] = failure;
// Merge output values
out[g[state][ch]] |= out[failure];
// Insert the next level node
// (of Trie) in Queue
q.add(g[state][ch]);
}
}
}
return states;
}
// Returns the next state the machine will transition to
// using goto and failure functions. currentState - The
// current state of the machine. Must be between
// 0 and the number of states - 1,
// inclusive.
// nextInput - The next character that enters into the
// machine.
static int findNextState(int currentState,
char nextInput)
{
int answer = currentState;
int ch = nextInput - 'a';
// If goto is not defined, use
// failure function
while (g[answer][ch] == -1)
answer = f[answer];
return g[answer][ch];
}
// This function finds all occurrences of
// all array words in text.
static void searchWords(String arr[], int k,
String text)
{
// Preprocess patterns.
// Build machine with goto, failure
// and output functions
buildMatchingMachine(arr, k);
// Initialize current state
int currentState = 0;
// Traverse the text through the
// built machine to find all
// occurrences of words in arr[]
for (int i = 0; i < text.length(); ++i) {
currentState = findNextState(currentState,
text.charAt(i));
// If match not found, move to next state
if (out[currentState] == 0)
continue;
// Match found, print all matching
// words of arr[]
// using output function.
for (int j = 0; j < k; ++j) {
if ((out[currentState] & (1 << j)) > 0) {
System.out.print(
"Word " + arr[j] + " appears from "
+ (i - arr[j].length() + 1) + " to "
+ i + "\n");
}
}
}
}
// Driver code
public static void main(String[] args)
{
String arr[] = { "he", "she", "hers", "his" };
String text = "ahishers";
int k = arr.length;
searchWords(arr, k, text);
}
}
|
更多：
标准模式搜索算法：
- 拉宾-卡普算法
- KMP 算法
- Z 算法（线性时间模式搜索算法）
- 有限自动机
- Boyer Moore 算法--坏特征启发式
- 阿霍-科拉希克模式搜索算法
- 从后缀数组构建 LCP 数组的 kasai 算法
- 检查流中回文的在线算法
- Manacher 算法 - 线性时间最长回文子串
- Ukkonen 的后缀树构造 - 第 1 部分
- 广义后缀树
