数据结构学习日志之八--模式匹配

xiaoxiao2021-02-28  10

字符串的模式匹配算法

Brute Force 算法:有两个字符串S和T,长度为N和M,首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和T[1]不相等,则T往右移动一个字符的位置,再依次进行比较。最坏的情况是进行M*(N-M+1)次比较,时间复杂度是O(M*N)

KMP算法:改进BruteForce算法,每当进行一次匹配过程中,不需要回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。

这个“滑动”距离取决于一个next数组,next数组决定了模式匹配串下次移动的距离。

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。用以下例子说明:

主串:abcababca...(假设主串很长,我们就先看前9位)子串:abcabx

按照传统的匹配模式的过程就应该如下:

传统的匹配模式,就应该是按照上面的方式一步一步的匹配下来,一旦匹配失败,主串指针i就要回溯,效率非常低!而KMP算法的匹配过程只需要两步:

为什么一下次就可以跳过中间的比较来到这一步呢,下面就来探究KMP算法的匹配方式。

先来对比一下传统的匹配模式,可以发现主串的指针i值的变化:

第一次遍历到了i=6,匹配失败;

第二次遍历到了i=2,匹配失败;

第三次遍历到了i=3,匹配失败;

第四次遍历到了i=4,匹配失败;

第五次遍历到了i=5,匹配失败;

直到第五次i值终于又回到了i=6。

i值的变化情况:6->1->2->3->4->5->6

在传统的匹配算法中,可以发现i值是不断回溯的。

反观KMP算法,只需对主串一次遍历,i值不会回溯,即遍历过程中i值是不会变小的。

那么既然KMP算法的i值遍历只需一次,那么就要考虑j是如何变化的了,为什么第一次匹配失败后j可以从j=3开始匹配,而不像传统遍历算法那样每当匹配失败就要从j=1重新开始匹配。

再看看一开始对KMP算法的定义:KMP算法的关键是<u>利用匹配失败后的信息</u>,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

划重点:<u>利用匹配失败后的信息</u>。什么是匹配失败后得到的信息呢?

于是回到刚刚的第一次匹配,看看能从这次失败的匹配中得到什么信息。

因为S[1...5] = T[1…5] 所以有 S[1,2] = T[1,2] S[4,5] = T[4,5]

又因为子串T有 T[1,2] = T[4,5],所以S[4,5] = T[1,2]

那下一次滑动到直接让S[4,5] = T[1,2],然后继续比较下一个元素就行啦。

这是简化模型第一次匹配的情况,根据传统的匹配算法,当匹配失败时模式串T移动一格,和S串比较。但是由于绿色部分在第一次匹配的时候发现了额外的信息:

就像刚刚那个例子,T[1,2] = S[4,5],都这样了,难道T还需要一格格的移动吗,直接滑过去就行啦。

这就是KMP算法的匹配过程。

如何确定模式串的滑动区间

知道了KMP算法的匹配过程,接下来就要考虑计算机是如何知道匹配失败时,指针j下一次指向的位置。由于KMP算法中指针i是不减的,因此j的指向位置只与模式串本身的结构有关。j的滑动位置的信息存放在next数组中。当匹配失败,就可以通过查询next数组的值得到下一次j滑动的位置。

next数组存放的是模式串的移位信息,具体就是模式串的部分匹配值,next数组大小与模式串T等长。

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

- "A"的前缀和后缀都为空集,共有元素的长度为0;

- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

下面是模式串T:a b c d a b c a | next数组的推导过程

j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 T[j]≠T[j] i++ next[i] = 0 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 T[j]≠T[j] i++ next[i] = 0 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 0 T[j]≠T[j] i++ next[i] = 0 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 0 1 T[j]=T[j] i++ j++ next[i] = j+1 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 0 1 2 T[j]=T[j] i++ j++ next[i] = j+1 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 0 1 2 3 T[j]=T[j] i++ j++ next[i] = j+1 j i 模式串:a b c d a b c a 串下标:0 1 2 3 4 5 6 7 next :0 0 0 0 1 2 3 T[j]≠T[j] j = next[j-1] j i 模式串:a b c d a b c a j :0 1 2 3 4 5 6 7 next :0 0 0 0 1 2 3 1 T[j]=T[j] next[i] = j+1 最后得到 next[] = {0,0,0,0,1,2,3,1}

C语言的next数组实现如下:

void get_next(String T,int next[]){ int j = 0; int i = 1; next[0] = 0; while(i<StrLength(T)){ if(T[i] == T[j]){ next[i] = j + 1; ++j; ++i; } else{ if(j!=0){ j = next[j-1]; } else{ next[i] = 0; ++i; } } } }

有了next数组,我们就可以知道每当KMP匹配过程中,一旦匹配失败,我们就令指针 j = next[j-1] ,然后继续与S[i]比较。

KMP完整算法如下:

int KMP(String S,String T){ int length_S = StrLength(S); int length_T = StrLength(T); int next[length_T]; get_next(T,next); int i = 0; int j = 0; while(j<length_T && i<length_S){ if(T[j] == S[i]){ ++i; ++j; } else{ if(j!=0) j = next[j-1]; else ++i; } } if(j==length_T) return i - length_T +1; return 0; }

转载请注明原文地址: https://www.6miu.com/read-2250116.html

最新回复(0)