当前位置：首页 > 编程日记 > 正文

字符串的模式匹配（朴素模式匹配算法，KMP算法）

编程日记 2024-10-15 22:30:00

字符串的模式匹配

寻找字符串p在字符串t中首次出现的起始位置

字符串的顺序存储

typedef struct
{char str[MAXSIZE];int length;
}seqstring;

朴素的模式匹配算法

基本思想：用p中的每一个字符去与t中的字符一一比较。

模式p 正文 t

如果匹配成功，则返回p在t中首次出现的起始位置

如果匹配不成功则返回-1

最坏情况比较次数可达：(n-m+1)*m次

int index(seqstring p,seqstring t)
{int i,j,flag;i=0;flag=0;while((i<=t.length-p.length) && (!flag)){j=0;flag=1;while(j<p.length && flag){if(p.str[j]==t.str[i+j]){j++;}else{flag=0;}}++i;}if(flag){return (i-1);}else{	return -1;}
}

或者另一种朴素模式匹配算法

int index(seqstring t,seqstring p)
{//t是文本串，p是模式串int i=0,j=0;while(i<t.length && j<p.length){if(p.str[j]==t.str[i]){i++;j++;}else{i=i-j+1;//需要琢磨j=0;}}if(j==p.length){return (i-j);}else{return -1;}
}

在学习KMP算法之前：

真前缀：除了自身以外，一个字符串的全部头部组合。

真后缀：除了自身以外，一个字符串的全部尾部组合。

（注意区分前缀和真前缀）

KMP算法的流程：

假设现在文本串S匹配到i位置，模式串P匹配到j位置

如果j==-1 或者当前字符匹配成功，则i++，j++，继续匹配下一个字符

如果匹配失败，那么模式串向右移动的位数：失配字符所在位置-失配字符对应的next值。

这时：j=6，next[j]=2，所以向右移动 j-next[j]=6-2=4个位置。

或者基于《最大长度表》：以匹配字符数-失配字符的上一位字符所对应的最大长度值

这时：以匹配字符为6，失配字符的上一位字符所对应的最大长度值=2，所以向右移动 6-2=4个位置。

int KMP_search(seqstring s,seqstring p,int next[])//文本串S，模式串P
{int i=0,j=0;while(i<s.length && j<p.length){if(j==-1 || s.str[i]==p.str[j]){//如果j=-1或者当前字符匹配成功，即s[i]==p[j]i++;j++;}else{//当匹配失败时，模式串向右移动的位数为：失配字符所在位置-失配字符对应的next值j=next[j];}}if(j==p.length){return (i-j);}else{return -1;}
}

在KMP算法中有一个next数组相当关键

所以首要的是求出next数组的各个值

next数组的求解：

求解基于“真前缀”和“真后缀”，next[i]最长相同的真前后缀的长度。

根据《最大长度表》求解next[ ]数组

例：对于字符串ABCDABD

《最大长度表》

字符	A	B	C	D	A	B	D
最大前后缀公共元素长度	0	0	0	0	1	2	0

next数组相当于最大长度表向后移一位，然后初始值赋值为-1。

可以不通过这个最大长度表直接计算next数组的值，即这个字符之前的字符串有多大长度的相同的前后缀（真前后缀）。

《next[] 数组》

i	0	1	2	3	4	5	6	7
模式串	A	B	C	D	A	B	D	\0
next[i]	-1	0	0	0	0	1	2	0

i=0时，对于模式串的首位，我们统一为next[0]=-1

i=1时，前面的字符为A，其最长相同真前后缀长度为0，next[1]=0

i=2时，前面的字符为AB，其最长相同真前后缀长度为0，next[2]=0

i=3时，前面的字符为ABC，其最长相同真前后缀长度为0，next[3]=0

i=4时，前面的字符为ABCD，其最长相同真前后缀长度为0，next[4]=0

i=5时，前面的字符为ABCDA，其最长相同真前后缀长度为1，next[5]=1

i=6时，前面的字符为ABCDAB，其最长相同真前后缀长度为2，next[6]=2

i=7时，前面的字符为ABCDABD，其最长相同真前后缀长度为0，next[7]=0

下面需要思考的是：如果知道了next[ j ]，怎么得到next [ j+1]呢？

next[ j ]=k，代表 j 之前的模式子串中，有长度为 k 的相同的前缀和后缀。

有了这个next[]数组，在KMP匹配中，当模式串 j 处失配时，模式串向右移动 j-next[j] 位。

1、对于模式串来说，如果p[ j ]==p[ k ]，那么next[j+1]=next[ j ]+1 = k+1（p[ k ]是前缀，p[ j ]是后缀）

这里 k=2，j=6，p[k]=p[j]，所以next[ j+1 ] = next[ j ]+1 = k+1 = 2+1 = 3。

2、如果p[ j ] != p[ k ]，那么就说明 “p0p1...pk-1pk” 不等于 “pj-k...pj-1pj”。

这里j=2，k=6，ABC!=ABD，那么在字符E前没有长度为k+1的相同的前后缀，需要去找一个长度更短一些的前后缀。

思路：与上面的模式串与文本串匹配类似（与KMP思路类似），当p0p1p2...pj跟主串s0s1...si匹配时，如果在模式串j处失配，则模式串需要向右移动 j-next[j] 位，相当于 j = next [ j ]。

而现在是前缀与后缀匹配，"p0p1..pk-1pk"和"pj-k...pj-1pj"匹配时，发现在pk处匹配失败，若能在前缀"p0...pk-1pk"中不断递归前缀索引k=next[k]，找到一个字符pk’==pj，且满足" p0pk'-1pk' "==" pj-k'pj-1pj "，则最大相同的前后缀长度为k'+1，从而next[j+1]=k'+1=next[k']+1。否则继续递归k'=next[k']，直到next[k']=0。

void getnext(seqstring p,int next[])
{int i=0;int j=-1;next[0]=-1;while(i<p.length){if(j==-1 || p.str[j]==p.str[i]){++i;++j;next[i]=j;}else{j=next[j];}}printf("未优化：\n");for(i=0;i<p.length;i++){printf("%5d",next[i]);}printf("\n");return ;
}

next数组的优化

应用上面的KMP算法，以及next[]数组的求解算法得到next数组中的各个值。

在下面这个例子中，因为 ‘c’和‘b’不匹配，所以模式串右移j-next[j]=3-1=2位。右移了两位后，又是b与c的匹配，显然也是不匹配的。那么出现这种情况的原因是：p[j]=p[ next[j] ]。因为p[j]!=p[i]，如果 p[ j ]==p[ next[ j ] ] ，那么必然会导致下一次匹配的失败，所以对求解next数组的函数进行进一步的优化。

void getnext(seqstring p,int next[])
{int i=0;int j=-1;next[0]=-1;while(i<p.length){//p[j]表示前缀，p[i]表示后缀if(j==-1 || p.str[j]==p.str[i]){++i;++j;//在前j+1个字符都匹配了以后，i+1，j+1，这时如果满足下面的if条件，则next[i]就是该字符之间的相同前后缀的长度if(p.str[j]!=p.str[i]){//如果两个不相同，就直接存储前面的子串的（以匹配的）长度next[i]=j;}else{//因为出现两个字符一样的情况，所以在使用KMP算法时，为了避免出现p[j]==p[next[j]]使算法效率变低，//所以当出现时需要递归，j=next[j]=next[next[j]].next[i]=next[j];}}else{j=next[j];}}printf("优化后：\n");for(i=0;i<p.length;i++){printf("%5d",next[i]);}printf("\n");return ;
}

只要出现了p[ next[ j ] ]=p[ j ]的情况，则把next[ j ]再次递归。例如在求模式串abab的next数组时，对于未优化的next数组，第二个a对应的值是0，相当于第二个a失配时，下一步匹配模式串会用p[ 0 ]处的a再次与文本串匹配，必然是失配的。所以再求第二个a的next值时，需要再次递归next[ 2 ]=next[ next[ 2 ] ]=next[0]=-1。此后，根据优化的新的next的值可知，第二个a失配时，执行" j==-1 || p.str[j]==p.str[i] ，++i，++j，继续匹配下一个字符 "，同理，对应的b的next的值为0。（可以自己手动推导，或者单步调试）。

对于优化后的next数组可以发现：如果模式串的后缀和前缀一样，例如abcdabcd，他们的前缀后缀都是abcd，其优化后的next数组是-1 0 0 0 -1 0 0 0，其前后缀的next值都是-1 0 0 0。

KMP算法的时间复杂度

回顾KMP算法的流程：

假设现在文本串S匹配到 i 的位置，模式串P匹配到 j 的位置

（1）如果j==-1 或者 S[ i ]==p[ j ]，就 i++，j++，继续匹配下一个字符

（2）如果 j != -1 && 当前的字符匹配失配，i不变（即 i 不回溯），j = next [ j ]，模式串向右移动了 j-next[ j ]位。

整个算法最坏的情况是：当模式串的首字符位于i-j的位置时才匹配成功

如果文本穿的长度为n，模式串的长度为m，匹配过程的时间复杂度是O(n)，求解next数组是O(m)，KMP算法的复杂度是O(m+n)。

有错的话，请大家及时指正！！！

参考文献：

1、从头到尾彻底理解KMP（2014年8月22日版）

2、从头到尾彻底理解KMP（2014年7月版）

3、《数据结构（C语言版）》，李云清杨庆红揭安全编著

4、KMP算法（1）：如何理解KMP

https://www.dkcj.cn/info/23208.html