商务合作:179001057@qq.com

字符串匹配

技术2022-05-12  2


某平台价值19860元的编程课程资料免费领取【点我领取】


kmp算法

设有主串s和子串t,子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t

传统的字符串模式匹配算法(也就是BF算法)就是对于主串和模式串双双自左向右,一个一个字符比较,如果不匹配,主串和模式串的位置指针都要回溯。这样的算法时间复杂度为Onm),其中nm分别为串s和串t的长度。

KMP 算法是由KnuthMorrisPratt等人共同提出的,所以成为KnuthMorrisPratt算法,简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比,KMP算法的不同点是匹配过程中,主串的位置指针不会回溯,这样的结果使得算法时间复杂度只为Onm)。下面说说KMP算法的原理。

假设我们有个模式串为“abdabcde”存于数组t,我们要求的就是模式串的next值,见下表所示:

 

i

0

1

2

3

4

5

6

7

t[i]

a

b

d

a

b

c

d

e

next[i]

-1

0

0

0

1

2

0

0

求模式tnext[i](称为失效函数)的公式如下:

 

 

next[i]= 

 

 

( 上面的公式中非t字母和数字组成的为数组下标)

应该如何理解next数组呢?在匹配过程中,如果出现不匹配的情况(当前模式串不匹配字符假定为t[i]),它所对应的next[i]的数值为接下来要匹配的模式串的字符的索引;也就是说,出现不匹配的情况时,模式串的索引指针要回溯到中next[i]所对应的位置,而主串的索引指针保持不变。

特别的,next数组中的next[0]next[1]的取值是固定的,为了标识出首字母,需要假定next[0]为-1(取为-1是考虑到C语言中的数组索引以0开始)。在实现的时候,要实现公式中情况的处理需要些技巧,下面给出具体的实现:

 

#include <stdio.h>  #include <stdlib.h>     typedef struct QString{      char *  cs;      int  len;  }String;    void GetNext(String s, int next [])  {      int len  =  s.len;      int i = 0 ;      int k = - 1 ;      next[0] = - 1 ;      while (i < len - 1 ){          if (k ==- 1 || s.cs[i] == s.cs[k]){              i ++ ;              k ++ ;              next[i] = k;          }else{              k = next[k];          }      }  }      int KMPIndex(String s, String m)  {      int next[m.len], i = 0, j = 0 ;      int k;      GetNext(m, next);      while (i < s.len && j < m.len){          if (j == - 1 || s.cs[i] == m.cs[j]){              i ++ ;              j ++ ;          }else{              j = next[j];          }      }      if(j >= m.len) return i - m.len;      else   return -1 ;  }  

 

KMP 算法也有需要改进的地方。对于模式串“aaaadd”在匹配时(假定被匹配串为“aaadddd”),可以看到,在匹配到索引3时,主串字符为“d”,模式串字符为“a”,如果按照上面的做法,这时模式串只会回溯一个索引,由于仍不匹配,模式串还会回溯一个索引,直到索引位置到了首字符,主串的索引指针才会前进一位,这样就会浪费一些不必要的比较时间。出现这种情况的原因是模式串中位置i的字符与next[i]对应的字符相同,需要修正next[i]next[i]对应的字符的索引。下面列出“aaaadd”修正的nextval数组的内容:

i

0

1

2

3

4

5

t[i]

a

a

a

a

d

d

next[i]

-1

0

1

2

3

0

nextval[i]

-1

-1

-1

-1

0

0

修正函数如下:

 

void GetNextval(String s, int nextval[])  {      int len = s.len, i = 0, k = -1 ;      nextval[0] = -1 ;      while (i  < len - 1){          if (k == - 1 || s.cs[i] == s.cs[k]){              i ++ ;              k ++ ;              if (s.cs[i] != s.cs[k]){                  nextval[i] = k;              }else                  nextval[i] = nextval[k];                      }else{              k = nextval[k];          }      }  }   


最新回复(0)