算法之字符串模式匹配

算法之字符串模式匹配

有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找呢?

假设主串target为: a b a c a a b a c a b a c a b a a b b,模式串pattern: a b a c a b(为了方便查看,每个字符间用空格隔开)。

用暴力算法匹配字符串过程中,我们会把target[0]pattern[0] 匹配,如果相同则匹配下一个字符,直到出现不相同的情况,此时我们会丢弃前面的匹配信息,然后把target[1]pattern[0] 匹配,循环进行,直到主串结束,或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法,极大地降低了匹配效率。

以上面的字符为例子:pattern的前5个字符abaca可以匹配target的前5个字符,但是pattern[5]target[5]不匹配。下面重新从target[1]开始和pattern匹配。

显然效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。

KMP

KMP算法是一种改进的字符串匹配算法,它的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。在KMP算法中,对于每一个模式串我们会事先计算出模式串的内部匹配信息,在匹配失败时最大的移动模式串,以减少匹配次数。

部分匹配表

正确的前缀:字符串中的所有字符,其中一个或多个字符被截断。“S”,“Sn”,“Sna”和“Snap”都是“Snape”的正确前缀。
正确的后缀:字符串中的所有字符,一个或多个字符在开头处截断。“agrid”,“grid”,“rid”,“id”和“d”都是“Hagrid”的正确后缀。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

  1. “A”的前缀和后缀都为空集,共有元素的长度为0;
  2. “AB”的前缀为[A],后缀为[B],共有元素的长度为0;
  3. “ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
  4. “ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
  5. “ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;
  6. “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;
  7. “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

KMP的关键是部分匹配表。这是模式abababca的部分匹配表:

1
2
3
4
5
# next 是指已经匹配的模式串子串中最长的相同的前缀和后缀,
# 如果 next [j] = k,代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
next: | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |

以index =3 为例,3之前的字符串是aba,最长的共有元素长度是1.

也意味着在某个字符失配时,该字符对应的 next值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到 next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j 之前的某个字符,而不是跳到开头,且具体跳过了k 个字符。

如何使用部分匹配表

假设我们将“abababca”模式与“bacbababaabcbab”相匹配。这里是我们的部分匹配表:

1
2
3
char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
next: | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |

我们第一次获得部分匹配是在这里:

1
2
3
4
# pattern[1]未匹配c成功,对c匹配pattern[next[1]]
bacbababaabcbab
|
abababca

此时部分匹配的长度index为1,next[index]的值为0,因此我们不会先跳过任何一个。我们得到的下一个部分匹配是:

1
2
3
4
# pattern[5]未匹配a成功,对a匹配pattern[value[5]]
bacbababaabcbab
|||||
abababca

这时index为5. next[index]的值为3.这意味着对当前字符匹配 pattern[next[index]]

1
2
3
4
5
#  x denotes a skip

bacbababaabcbab
xx|||
abababca

此时继续匹配失败,index=3,next[index]的值是0.这意味着对当前字符匹配 pattern[next[index]]即从头开始匹配.

1
2
3
4
5
// x denotes a skip

bacbababaabcbab
xx|
abababca

此时,我们的模式比文本中的其余字符长,所以我们知道没有匹配。

如何计算

从上面的详细描述,我们可以得到算法逻辑的重点在于获取部分匹配表,下面是计算方法:

  • 已知next[j] = k,next[0] = 0,如何求出next[j + 1]
    • 如果pattern[k]==pattern[j],则next[j+1] = next[j]+1=k+1;
    • 如果pattern[j] != pattern[k],
      • k=next[k],如果此时pattern[k]==pattern[j],则next[j+1] = k+1;
      • 如果仍不相等,继续递归前缀索引,令k=next[k],继续判断pattern[k]==pattern[j],知道k=-1,或pattern[k]=pattern[j]为止。

注意,k=next[k]很巧妙,利用了之前的next[?]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 从模式中提取 next 数组
public void getNextArray(char[] pattern,int[] next) {
next[0]= -1; // index为0的字符前无字符串
for (int j = 0; j < pattern.length-1; ++j) {
// pattern[0~k-1] 与pattern[j-k ~ j-1] 相同
// 如果pattern[j] 匹配失败,下一步匹配 pattern[k].
int k = next[j];
while (k > 0 && pattern[k] != pattern[j]) {
k = next[k];
}
if (k == -1) {
next[j + 1] = 0;
continue;
}
if (pattern[k] == pattern[j]) {
// 如果pattern[j+1] 匹配失败,下一步匹配 pattern[k+1].
// 但是如果 pattern[j+1] == pattern[k+1],这一步是可以省略的.直接判断 next[k+1]
next[j + 1] = next[k+1];
}
}
}

public int indexOf(String target,String pattern){
int i=0;int j=0;
int tLength = target.length();
int pLength = pattern.length();
if(tLength < pLength){
return -1;
}
int[] next = new int[pattern.length()];
getNextArray(pattern.toCharArray(),next);

while (i<tLength && j<pLength){
//如果j = -1,或者当前字符匹配成功(即target[i] == pattern[j]),令i++,j++
if (j == -1 || target.charAt(i) == pattern.charAt(j)){
i++;
j++;
} else {
//如果j != -1,且当前字符匹配失败(即target[i] != pattern[j]),则令 i 不变,j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLength) {
// 匹配成功
return i - j;
}
else {
return -1;
}
}

如果某个字符匹配成功,模式串首字符的位置保持不动,仅仅是i++、j++;如果匹配失配,i 不变(即 i 不回溯),模式串会跳过匹配过的next[j]个字符。整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功,算法结束。所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为O(n),算上计算next的O(m)时间,KMP的整体时间复杂度为O(m + n)。

BM

KMP的匹配是从模式串的开头开始匹配的,而1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法:Boyer-Moore算法,简称BM算法。该算法从模式串的尾部开始匹配,且拥有在最坏情况下O(N)的时间复杂度。在实践中,比KMP算法的实际效能高。

-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%