首页 / 软件开发 / 数据结构与算法 / KMP模式匹配算法分析与实现

KMP模式匹配算法分析与实现2010-11-19 csdn liguisen基本概念：

模式匹配是对字符串的一种非常重要的操作，假设被匹配的正文字符串是 text，模式串是pattern，则模式匹配的任务就是在text中找出所有的pattern， 给出pattern在text中的位置。

例如：text是“cdghcdghhcdr”，pattern是“cd”， 则答案是0，4，9（下标计数从0开始）

简单字符匹配：

第1轮：

用pattern的第1个字符与text的第1个字符比较，不等就结束，相等就

用pattern的第2个字符与text的第2个字符比较，不等就结束，相等就 ……

第2轮：

用pattern的第1个字符与text的第2个字符比较，不等就结束，相等就

用pattern的第2个字符与text的第3个字符比较，不等就结束，相等就 ……

……

这种做法非常直观，实际上就是把模式串pattern放到正文text的各个位置逐 一匹配，假设text、pattern的长度分别是m、n，则上述做法总共有m轮，每一轮 比较n次，所以该算法的时间复杂性是O（mn）。

KMP模式匹配：

简单匹配法在一次字符比较失败后，只是向前移动一个位置，丢掉了由前面 已做过的字符匹配的信息，当模式串pattern后面部分与前面部分有重复（匹配 ）时，一次可以移动多个位置。

考虑如下例子：

表1

位置i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

正文text

c

a

g

a

c

a

g

a

c

a

g

a

t

a

模式pattern

a

g

a

c

a

g

a

t

a