KMP字符串匹配算法

时间:2023-01-07 18:39:08

一、概要:

  KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的(先了解BF算法)。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

二、怎么求模式串next[n]的值:

  定义:

1)next[0]= -1  意义:任何串的第一个字符的模式值规定为-1。

2)next[j]= -1   意义:模式串T中下标为j的字符,如果与首字符

相同,且j的前面的1—k个字符与开头的1—k

个字符不等(或者相等但T[k]==T[j])(1≤k<j)。

如:T=”abCabCad” 则 next[6]=-1,因T[3]=T[6]

3)next[j]=k    意义:模式串T中下标为j的字符,如果j的前面k个

字符与开头的k个字符相等,且T[j] != T[k] (1≤k<j)。

                       即T[0]T[1]T[2]。。。T[k-1]==

T[j-k]T[j-k+1]T[j-k+2]…T[j-1]

T[j] != T[k].(1≤k<j);

(4) next[j]=0   意义:除(1)(2)(3)的其他情况。

 

  举例:

01)求T=“abcac”的模式函数的值。

     next[0]= -1  根据(1)

     next[1]=0   根据 (4)   因(3)有1<=k<j;不能说,j=1,T[j-1]==T[0]

     next[2]=0   根据 (4)   因(3)有1<=k<j;(T[0]=a)!=(T[1]=b)

     next[3]= -1  根据 (2)

     next[4]=1   根据 (3)  T[0]=T[3] 且 T[1]=T[4]

    即   

下标

0

1

2

3

4

T

a

b

c

a

c

next

-1

0

0

-1

1

T=“abcab”将是这样:

下标

0

1

2

3

4

T

a

b

c

a

b

next

-1

0

0

-1

0

为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)” 且T[j] != T[k]”被划入(4)。

02)来个复杂点的,求T=”ababcaabc” 的模式函数的值。

next[0]= -1    根据(1)

         next[1]=0    根据(4)

         next[2]=-1   根据 (2)

next[3]=0   根据 (3) 虽T[0]=T[2] 但T[1]=T[3] 被划入(4)

next[4]=2   根据 (3) T[0]T[1]=T[2]T[3] 且T[2] !=T[4]

next[5]=-1  根据 (2) 

next[6]=1   根据 (3) T[0]=T[5] 且T[1]!=T[6]

next[7]=0   根据 (3) 虽T[0]=T[6] 但T[1]=T[7] 被划入(4)

next[8]=2   根据 (3) T[0]T[1]=T[6]T[7] 且T[2] !=T[8]

 即

下标

0

1

2

3

4

5

6

7

8

T

a

b

a

b

c

a

a

b

c

next

-1

0

-1

0

2

-1

1

0

2

只要理解了next[3]=0,而不是=1,next[6]=1,而不是= -1,next[8]=2,而不是= 0,其他的好象都容易理解。

03)   来个特殊的,求 T=”abCabCad” 的模式函数的值。

下标

0

1

2

3

4

5

6

7

T

a

b

C

a

b

C

a

d

next

-1

0

0

-1

0

0

-1

4

         

next[5]= 0  根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]

next[6]= -1  根据 (2) 虽前面有abC=abC,但T[3]==T[6]

next[7]=4   根据 (3) 前面有abCa=abCa,且 T[4]!=T[7]

T[4]==T[7],即T=” adCadCad”,那么将是这样:next[7]=0, 而不是= 4,因为T[4]==T[7].

下标

0

1

2

3

4

5

6

7

T

a

d

C

a

d

C

a

d

next

-1

0

0

-1

0

0

-1

0

 

如果你觉得有点懂了,那么

练习:求T=”AAAAAAAAAAB” 的模式函数值,并用后面的求模式函数值函数验证。

 

意义

 next 函数值究竟是什么含义,前面说过一些,这里总结。

设在字符串S中查找模式串T,若S[m]!=T[n],那么,取T[n]的模式函数值next[n],

1.       next[n]=  -1 表示S[m]和T[0]间接比较过了,不相等,下一次比较 S[m+1] 和T[0]

2.       next[n]=0 表示比较过程中产生了不相等,下一次比较 S[m] 和T[0]。

3.       next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了,下一次比较S[m]和T[k]相等吗?

4.       其他值,不可能。

 

三、代码:

KMP字符串匹配算法KMP字符串匹配算法
 1 <?php
2 //求next值
3 function get_nextval($s)
4 {
5 $next[0] = -1;
6 $j = 0;
7 $k = -1;
8
9 $length = strlen($s);
10 while($j<$length-1)
11 {
12 if($k==-1 || $s[$j]==$s[$k])
13 {
14 ++$j;
15 ++$k;
16 if($s[$j]!=$s[$k])
17 {
18 $next[$j] = $k;
19 } else {
20 $next[$j] = $next[$k];
21 }
22 } else {
23 $k = $next[$k];
24 }
25 }
26 return $next;
27 }
28
29 function kmp($s, $t, $pos=0)
30 {
31 $i = $pos;
32 $j = 0;
33 $slength = strlen($s);
34 $tlength = strlen($t);
35 $next = get_nextval($t);
36 $index = 0;
37 while($i<$slength && $j<$tlength)
38 {
39 if($s[$i]==$t[$j])
40 {
41 $i++;
42 $j++;
43 } else {
44 if(-1==$next[$j])
45 {
46 $i++;
47 $j = 0;
48 } else {
49 $j = $next[$j];
50 }
51 $index = $i;
52 }
53 }
54 if($j == $tlength)
55 {
56 return $index;
57 } else {
58 return false;
59 }
60 }
61
62 $t = "abCabCad";
63 $s = "abCabCaabCabCad";
64 $index = kmp($s, $t);
65 var_dump($index);
View Code