[Algorithm] 字符串匹配： MP，KMP，暴力搜索等(ZT)

2024-01-05 03:32
文章标签 搜索 字符串 匹配 kmp 暴力 mp algorithm zt

本文主要是介绍[Algorithm] 字符串匹配： MP，KMP，暴力搜索等(ZT)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Contents

  • 1   Prologue
  • 2   Notations
  • 3   Main Idea
  • 4   MP 算法
    • 4.1   原理
    • 4.2   跳转数组的计算
    • 4.3   另一种表示
    • 4.4   可是...
  • 5   KMP 算法
  • 6   复杂度分析
  • 7   KMP 算法的最长停顿
  • 8   为什么费波拉契串这么神奇
  • 9   PS
  • 10   References

1   Prologue

本篇文章主要针对的是对字符串匹配有兴趣的生物以及被某版本数据结构与算法教材中的 KMP 算法讲解弄得不知所云但与此同时却还难能可贵地保持着旺盛求知欲的不幸生在了错误年代的可怜童鞋，其他生物阅读本文前请慎重考虑因为它 可能对您的大脑（如果有）、小脑甚至包括脊髓都造成严重且不可恢复的创伤 。

2   Notations

下文可能会提到 “模式串”、“文本串”、“窗口” 这些词，它们的定义如下，如果这些文字使你头晕，请及时做好救治准备。

模式串、文本串
所谓  模式串 ，是指你想要找到（或者得到位置 &etc.）的字符串；而  文本串 ，则是指搜索的目标字符串。
比如说你要在 " lucky dog" 中寻找 " dog" ，那么 " dog" 是模式串， " lucky dog" 则是文本串；
而你若要在 " If is a lucky dog" 中寻找 " lucky dog" ，那么 " lucky dog" 便成了模式串， " If is a lucky dog" 则是文本串。

Understand?

窗口
无论用什么样的搜索算法，在搜索的过程中，总是需要将模式串与文本串进行比较，它们对齐的那部分区域，也就是们关心的那块区域，咱称为  窗口 。

另外，为了避免让已经适应 C/C++/C#/D/Java/JavaScript/Python/Go/... 语言思维的童鞋多绕一个弯，本文用到的数组下标都以 0 开始 —— 甚至包括费波拉契数列也如此。

3   Main Idea

MP/KMP 字符串搜索算法的思想精华在于利用已经匹配的部分包含的信息，加速搜索的过程。

嗯——已经匹配的部分包含什么信息？

它已经匹配了！

举例说，在某个字符串中查找子串 A B C D A B D A C 时，如果遇到 A B C D A B ，而紧跟其后的不是 D ，这时候我们可以将窗口右移四位（而不是一位），因为既然 A B C D A B 已经匹配了， 那么移动当前窗口之后 已经匹配过的地方 肯定需要保证 依然匹配 ，这里最好的做法即让 A B 相互对齐:

. . A B C D A B ? . . . . . .
    A B C D A B D A C

=>

. . A B C D A B ? . . . . . .
            A B C D A B D A C

因为，看呀，如果只右移一位，那么:

. . . . . . . . . . . . . . . // 先不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>    A B C D A B D A C
      |
    糟糕！

如上面所示， A B C D A B 匹配了，那么移动一位之后，第一个字符 A 就肯定会对着 B ，绝对不可能在这个地方找到匹配

右移两位、三位或者四位时发生的状况可以依此类推；而右移四位时就不同了:

. . . . . . . . . . . . . . . // 暂时还不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>          A B C D A B D A C

这个时候才 可能 成功匹配。

4   MP 算法

4.1   原理

MP 算法基于这样一种观察：

Note

注意了，这里以及下面所说的 前缀 和 后缀 都是指 不包括自身 的“真”前缀或后缀 ( proper prefix/suffix )

发生了不匹配之后，移动窗口时，定要保证 将模式串已匹配部分的一个前缀和一个相同的后缀对齐，并使这个前缀尽可能长 。

什么意思？

首先让我们列出模式串 A B C D A B 的所有前缀：

0: /*Empty*/
1: A
2: A B
3: A B C
4: A B C D
5: A B C D A

我们再列出它所有的后缀：

0: /*Empty*/
1: B
2: A B
3: D A B
4: C D A B
5: B C D A B

发现前缀 A B == 后缀 A B ，将它们对齐（即，接下来直接从第 3 位开始比较），完美了，前两位不必重复比较了。

原理上说也不难理解： 从左向右移动窗口的过程就是用前缀去匹配后缀的过程 ，而第一次匹配成功的肯定是最长的相同前缀/后缀 —— 在上例中，两个空字串也相等，可是如果将它们对齐的话那可就“移过头了”。

这么看，我们发现，在模式串的每一个位置上，匹配失败之后能最大限度的将窗口移动多少位 —— 即，与什么位置对齐， 只与模式串在该位置前方的子串有关 ，与文本串无关，与模式串在该点之后的字符也无关。

于是，自然而然的就想到了，为什么不把这么个失败后对齐的位置存放在一个数组中呢，这样每次匹配失败之后就按照它的指示进行跳转。

令 F[i] == max{ j | pattern[0:j) == pattern[i-j+1:i+1) and 0<j<i }<="" cite="" style="word-wrap: break-word;"> ，也就是当前位置上保证前缀等于后缀的最大长度。

对于模式串 A B C D A B D A C , F 数组如下：

Index012345678
PatternABCDABDAC
F000012010

继续扯，在位置 i 匹配失败之后，可以将窗口继续右移一位，并从 F[i-1] 位置开始继续比较模式串与文本串（按照定义，pattern[ 0 : F[i-1] ) 已经保证匹配了），用代码表示的话就是这样：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            // 第一个字符不匹配则右移窗口、从 0 开始比较
            if (j==0) {
                j=-1;
                break;
            }
            j = F[j-1]; // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

—— 多和谐呀！



对了，内个 F 数组怎么算？

4.2   跳转数组的计算

观察一下，希望求出拥有相同后缀的最长前缀，这个过程不也是一个字符串匹配的过程吗：

1.  A B C D A B D A C
    A B C D A B D A C
    |
    0  // 定义为 0

2.    A B C D A B D A C
    A B C D A B D A C
      |
      0 // 匹配部分的长度

3.      A B C D A B D A C
    A B C D A B D A C
        |
        0

4.        A B C D A B D A C
    A B C D A B D A C
          |
          0

5.6.        A B C D A B D A C
    A B C D A B D A C
            | |
            1 2

7.              A B C D A B D A C
    A B C D A B D A C
                |
                0

8.                A B C D A B D A C
    A B C D A B D A C
                  |
                  1

9.                  A B C D A B D A C
    A B C D A B D A C
                    |
                    0

如上面所示，将模式串向右移动，并与自身做比较，在位置 i 上，pattern[i:] 与 pattern 自身相匹配的部分的长度就是 F[i] 。

注意第6步到第7步！ 为什么可以直接右移两位呢？

—— 因为 F[1] 已经算出来了！于是我们可以将之前 MP 算法中的思想用在这里，聪明的你想到了没有？

用代码来说就是这样的，看不懂的话我会很伤心：

void calcF(char const* pattern, int* F)
{
    int i=0,j=0;
    for(;pattern[i];++i,++j) {
        while(j>0 && pattern[j-1]!=pattern[i]) {
            j = F[j-1];
        }
        F[i] = j;
    }
}

4.3   另一种表示

对了有没有人觉得 MP 算法中对于第一个字符不匹配时的特殊处理感觉到很生硬的？

嗯，其实呢，考虑到第一个字符失败时的特殊情况其实也不怎么特殊，不如干脆把这种情况也放到 F 数组中去统一处理好了：

Index0123456789
PatternABCDABDAC 
F-1000012010

这样，MP 算法表达起来更简单了：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];   // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

calcF 也并没有因此变复杂：

void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

理解之后就会觉得，这种表示方法比较 “省事”；下面咱就都用这种表示得了。

Nevertheless, 其实它们是一码事。

4.4   可是...

我们再停下来看看 “暴力” 搜索算法 —— 有没有可能暴力算法比 MP 算法还快呢？

答案是 “Yes!”

( 哈哈！你输了吧！ )




让我们想象一下在一个字符集很大的串 —— 比如说 UTF-16 字符串吧，中寻找一段模式串；而模式串的第一个字符出现在文本串中的频率根本就不大，那么看看第一次匹配失败时它们两者工作的流程吧：

MP 算法暴力算法
  1. i>=n?
  2. j>=0? ( 此时 j == 0 )
  3. 比较 pattern[j] 与 text[i]
  4. j = F[j]
  5. j>=0? ( 此时 j == -1 )
  6. j = j+1
  7. j >= m?
  8. i = i+1
  9. 到第 1 步
  1. i>=n?
  2. j = 0
  3. j < m?
  4. 比较 pattern[j] 与 text[i]
  5. i = i+1
  6. 到第 1 步

嗯，所以说，这个地方是有优化空间的，Knuth、Morris、Pratt 的论文 [1] 中有提到，俺就不展开了 —— 因为真正牛B的优化在下面：




5   KMP 算法

其实 MP 算法的效率还有提升的空间，不过从模式串 A B C D A B D A C 中看不明显；我们试试这样一个模式串： A B A B A B C 。

假设在 A B C A B C A B A B A B C A C 中查找 A B A B A B C ，按照 MP 算法的思想，先算出 F 数组：

PatternABABABC 
F-10012340

于是查找的过程就是这样的：

1.  A B C A B C A B A B A B C A C
    A B A . . . .

2.  A B C A B C A B A B A B C A C
        A . . . . . .

3.  A B C A B C A B A B A B C A C
          A B A . . . .

4.  A B C A B C A B A B A B C A C
              A . . . . . .

5.  A B C A B C A B A B A B C A C
                A B A B A B C

从第 1 步到第 2 步、从第 3 步到第 4 步，我们发现，字符 A 与 C 的不匹配导致了第一次失败，然后紧接着又直接导致了第二次失败。

如此，我们又惊喜的发现，在 A B 之后若是遇到不是 A 的字符，我们完全可以跳三步！因为跳两步的话算是把 A 对齐了 —— 可是它们会被对齐到一个不是 A 的、将会导致匹配失败的字符上面去。

这样的规则有什么规律呢？我直接放出代码吧：

// 这是我们计算 MP 算法中的 F 数组的函数：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

睁大眼睛准备找茬喽：

// 只需要改一句话：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        // !这里!
        F[i+1] = pattern[j+1] == pattern[i+1]?
                   F[j+1]:
                   j+1;
    }
}

为什么呢？因为对于同一个字符导致的失败，失败在前面应该跳到哪里，到后面就还是应该跳到哪里。

另外，这个时候咱似乎就比较喜欢把这个数组称作 next 数组了 —— 其实还是同一回事。

那么， A B A B A B C 的 next 数组如下，请您欣赏：

Index0123456 
PatternABABABC 
Next-10-10-1040

6   复杂度分析

至于为什么 KMP 算法的复杂度是线性的，我们再回头看看 另一种表示 一节中的算法主体：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F);
    for(;text[i];++i,++j) { // j 增大，i 增大
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];       // j 减小
        }
        if(j>=m-1) {
            return (i+1-m);
        }
    }
    return -1;
}

i 只有增大的份，所以 ++i 最多执行 n 次，这个很显然。

j 初始值为 0，一共增加了 n 次，而 j>=-1 ，于是 j = F[j] 这一句最多也就执行了 n+1 次（否则就会出现 j<-1 的情况了）。

所以就是线性的了！

7   KMP 算法的最长停顿

为了说明 KMP 算法在文本串上的某一个字符上进行了很多次比较的极限情况（也就是所谓的停顿或者E文的 delay ），我们首先要介绍一下 “费波拉契串” —— 因为，很巧，它就是能使 KMP 算法达到最糟糕状况的模式串，一会儿我们会说到。

提到 “费波拉契” ，相信不少人会直接想到 1, 1, 2, 3, 5, 8, 13, 21, 34 ... ，是的，费波拉契串的定义也十分类似：

设 P 是个费波拉契串，那么：

P[0] = b
P[1] = a
P[i] = P[i-1]P[i-2]

所以：

P[2] = ab
P[3] = aba
P[4] = abaab
P[5] = abaababa
P[6] = abaababaabaab
P[7] = abaababaabaababaababa
P[8] = abaababaabaababaababaabaababaabaab
...

计算出 P[7] 的 F 数组和 Next 数组如下，我们一会儿要用到，你也可以先把它当作找规律的题看看：

Pabaababaabaababaababa 
n0123456789101112131415161718192021
F-100112323456456789101178
Next-10-110-13-110-160-13-110-111-18

费波拉契串有几个性质值得注意一下：

Note

文章前面已经假设了我的世界里费波拉契数列下标是从 0 开始的，这里再强调一遍。

  1. strlen(P[n]) == Fibonacci[n] （这个应该很容易理解吧）

  2. 设函数 c(t) 的作用是交换字符串 t 的最后两个字符，例如 c("abcdef") == "abcdfe"，那么当 n>=2 时 P[n-1]P[n-2] == c(P[n-2]P[n-1]) ：
    n == 2 时这是显然的；
    当 n>2 时可以用数学归纳法证明：
    c(P[n-2]P[n-1]) = P[n-2]c(P[n-1]) = P[n-2]P[n-3]P[n-2] = P[n-1]P[n-2]
  3. 由上面两条性质我们又可以推导出：
    Next[Fibonacci[n]-2] == F[Fibonacci[n]-2] == Fibonacci[n-1]-2, n>=2
    这是因为，可以把一个费波拉契串分解开：
    P[n] == P[n-1]P[n-2] == P[n-2]P[n-3]P[n-2] == c(P[n-3]P[n-2])P[n-2] == P[n-3]c(P[n-2])P[n-2] == ...
    具体以 P[7] 为例，
    P[7] ==  ab-ab-ba---ab------ba
    其中省略掉的部分根据  性质2 表现出的规律与前方相等，因此如果在 P[7] 的最后一个字符 b 处发生了不匹配，接下来应该在下列位置重新试着匹配：
    ab-a--b----a-------b-
    它们正好占据着 Fibonacci[2]-2, Fibonacci[3]-2, .. , Fibonacci[7]-2, ... 的位置。

因此，如果在费波拉契串的第 n 位，n == Fibonacci[k]-2 上发生了不匹配，接下来则还需要 k-1 次比较；

又因为 Fibonacci[k-1] == (φk - (-1)kφ-k)/sqrt(5) == round( φk / sqrt(5) )， 于是可以解得 k ~ logφ(n)，其中 φ 是黄金比例 (1+sqrt(5))/2 == 1.618...

—— k 便是文本串上的一个字符的最多比较次数。

8   为什么费波拉契串这么神奇

为了证明为何费波拉契串就是使停顿时间最长的模式串，我们再看看 MP 算法的基本思想：将字符串已匹配的一个前缀和一个对应的后缀匹配。

假设字符串 S 有且仅有一个相等的前缀和后缀（设为 a ），那么 S 可以表示为

S = aB = Ca

再假设 a 本身也有且仅有一个相等的前缀和后缀（设为 e ），那么 a 也可以表示为

a = eF = Ge

对应 MP 算法，匹配 Ca 时若在 a 之后失败，则会将 aB 的 a 与其对齐：

Cax
Cay

==>

Cax
 aBy

若在 B 的第一个字符处再次失败，则下一次对齐是这样的：

CGex
 GeBy

==>

CGex
  eFBy

KMP 算法在这里还要求 F 的第一个字符和 B 的第一个字符不等（否则会跳过这一段）

我们很容易可以证明想要 KMP 算法在这个地方停留尽可能长的时间需要满足 |S| <= |e| + |a| ：因为若 |e| + |a| > |S|，那么令 d = |e| + |a| - |S| 则 Ca = CGe = aB 算式中， a 和 e 将有长度为 d 的重叠，于是 B 的第一个字符等于 e[d]；同理，在 aB = eFB = Ca 算式中，可以得到 F 的第一个字符为 a[d]，由 a = eF 可以得到 a[d] = e[d]，和 KMP 的要求不符。

于是 |S| == |e| + |a| 是使 KMP 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

9   PS

对了，如果我要找出模式串在文本串中所有的出现怎么办？

提示一下：目前为止 F 数组（或者 next 数组）的最后一个元素我们还没有用到过是不是？

10   References

[1]KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350.
[2]http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
[3]http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

Last update: 2010/11/23 18:53:11

这篇关于[Algorithm] 字符串匹配： MP，KMP，暴力搜索等(ZT)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/571525。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
关于Gateway路由匹配规则解读

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由
阅读更多...
C#从XmlDocument提取完整字符串的方法

C#从XmlDocument提取完整字符串的方法

《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,... 方法1：通过XMLDocument的OuterXml属性，见XmlDocument类该方法获得的xm
阅读更多...
JSON字符串转成java的Map对象详细步骤

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》：本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添
阅读更多...
Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
python修改字符串值的三种方法

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法：第二种方法：第三种方法：在python中，字符串对象是不可变类型，所以我们没办法直接
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
C#中字符串分割的多种方式

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2