基于MATLAB的数据结构与算法-KMP课件

基于MATLAB《数据结构与算法》ß延边大学信息管理专业(13级)ß崔基哲KMP模式匹配算法MATLAB编程之基础算法3串的模式匹配算法一、基本概念1、模式匹配（定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置（定位）3、算法种类KMP算法KMP模式匹配算法✱

它是：在一个长字符串中匹配一个短子串的无回溯算法。定义✱

s:模式串,m:模式串的长度✱

text:要匹配的字符串,n:text的长度✱

设text:x1,x2,…xn,s:a1,a2,…am,则当存使xi+k=ak(k=1,2,…m)时，认为text与模式串匹配，当然text也可能与模式串有多处匹

配✱

例如：text:abcabca,s:abc则text与s匹配位置有3和6KMP算法✱作为一种无回溯的算法，它是高效的，待会儿你将看到它的时间复杂度为O(m+n)，空间复杂度也为O(m+n)✱而且，它很容易理解，代码也很短定义✱

next:为对应模式串的数组✱

设字符串为s1s2s3...sm,其中s1，s2，s3，...si，...sm均是字符，则next[i]=m，当且仅当满足如下条件：字符串s1s2...smequals字符串s(i-m+1)...si-1

si并且

s1s2...sm

s(m+1)unequals

s(i-m)s(i-m+1)...si-1

si。✱

通俗地讲，next[i]保存了以s[i]为结尾的后与模式串前缀的最长匹配数。KMP算法的运行过程✱

我们用两个指针i和j分别表示，A[i-j+1..i]与B[1..j]完全也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。✱

如果a[i+1]==b[j+1],i和j各加1，什么时候j==m，就说B是A的子串（B串已经整完了）KMP算法的运行过程✱

如果a[i+1]!=b[j+1],这时候怎么办？✱

i

=

1

2

3

4

5

6

7

8

9

……✱

A

=

a

b

a

b

a

b

a

a

b

a

b

…✱

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7j=5时，a[i+1]!=b[j+1],我们要把j改成比它小的值j‘。改多少合适呢？KMP算法的运行过程✱

i

=

1

2

3

4

5

6

7

8

9

……✱

A

=

a

b

a

b

a

b

a

a

b

a

b

…✱

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7✱

记住，我们要保持A[i-j+1..i]与B[1..j]完全相等，因而j’最大的数使a[i-j’+1..i]与B[1..j’]完全相等.KMP算法的运行过程✱

i

=

1

2

3

4

5

6

7

8

9

……✱

A

=

a

b

a

b

a

b

a

a

b

a

b

…✱

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7✱

显然是求一个最长的以i为末尾的后缀要与B的前缀匹配。由于A[i-j+1..i]与B[1..j]完全相等,故令j’=next[j]即可性质保留KMP算法的运行过程✱

i

=

1

2

3

4

5

6

7

8

9

……✱

A

=

a

b

a

b

a

b

a

a

b

a

b

…✱

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7✱

i

=

1

2

3

4

5

6

7

8

9

……✱

A

=

a

b

a

b

a

b

a

a

b

a

b

…✱B

=

a

b

a

b

a

c

bj

‘=

1

2

3

4

5

6

7KMP算法的运行过程✱

需要注意的是i并没有动，改变的只是j的值✱

如果改变j的值后a[i+1]仍不等于b[j+1]的话，继续改变j值直到a[i+1]==b[j+1]或者j=0✱

j=0表示i+1前面无论怎么匹配都不能使

a[i+1]==b[j+1],只好让a[i+1]与b[j+1]单独匹配✱

还是上一个例子，再演示一下KMP算法的运行过程✱✱i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…✱✱B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7✱

当i=6,j=5时，a[i+1]!=b[j+1],故令

j=next[5]=3KMP算法的运行过程✱✱i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…✱✱B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7✱

此时i=6,j=3仍不满足a[i+1]==b[j+1]，故继续减小j,使j=next[3]=1KMP算法的运行过程✱✱i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…✱✱B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7✱

此时i=6,j=1仍不满足a[i+1]==b[j+1]，故继续减小j,使j=next[1]=0KMP算法的运行过程✱✱i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…✱✱B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7✱

终于，A[8]=B[1]，i变为8，j为1KMP算法的运行过程✱✱i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

d

b

a

b

…✱✱B