KMP模式匹配算法分析与实现
作者：liguisen
http://blog.csdn.net/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 |
|
|
|
|
|
|
|
模式pattern后面有aga（第4到第6）与最前面aga（第0到第2）重复（匹配）
位置0不匹配，从位置1开始，匹配在正文text的第8个位置失败，如表2：
表2
|
位置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 |
|
|