KMP算法

浏览数：22 / 时间：2015年06月08日

Knuth-Morris-Pratt算法（简称KMP），以三个发明者命名，起头的那个K就是著名科学家Donald Knuth

一、什么是KMP算法

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next
值（next 数组的求解为核心），即移动的实际位数为：j - next[j]，且此值大于等于1。

二、应用实例

#1015 : KMP算法

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。

这一天，他们遇到了一只河蟹，于是河蟹就向小Hi和小Ho提出了那个经典的问题：“小Hi和小Ho，你们能不能够判断一段文字（原串）里面是不是存在那么一些……特殊……的文字（模式串）？”

小Hi和小Ho仔细思考了一下，觉得只能想到很简单的做法，但是又觉得既然河蟹先生这么说了，就肯定不会这么容易的让他们回答了，于是他们只能说道：“抱歉，河蟹先生，我们只能想到时间复杂度为（文本长度 * 特殊文字总长度）的方法，即对于每个模式串分开判断，然后依次枚举起始位置并检查是否能够匹配，但是这不是您想要的方法是吧？”

河蟹点了点头，说道：”看来你们的水平还有待提高，这样吧，如果我说只有一个特殊文字，你能不能做到呢？“

小Ho这时候还有点晕晕乎乎的，但是小Hi很快开口道：”我知道！这就是一个很经典的模式匹配问题！可以使用KMP算法进行求解！“

河蟹满意的点了点头，对小Hi说道：”既然你知道就好办了，你去把小Ho教会，下周我有重要的任务交给你们！“

”保证完成任务！”小Hi点头道。

提示一：KMP的思路

提示二：NEXT数组的使用

提示三：如何求解NEXT数组

输入

第一行一个整数N，表示测试数据组数。

接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

输出

对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

样例输入

5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD

样例输出

3
1
3
1
0

 1 /*
 2 ****************************T*******KMP算法*******************************************
 3 ******************************by JA/C++ 2015-1-13****************************************
 4 */
 5 
 6 
 7 #include <cstdio>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <cstring>
11 #include <string>
12 #include <vector>
13 using namespace std;
14 
15 int KMP(string t, string p){
16     int pLen = p.size();
17     vector <int> next(pLen + 1, 0);
18     next[0] = -1;
19     int k = -1;
20     int j = 0;
21     while (j < pLen - 1)
22     {
23         //p[k]表示前缀，p[j]表示后缀    
24         if (k == -1 || p[j] == p[k])
25         {
26             ++j;
27             ++k;
28             //较之前next数组求法，改动在下面4行  
29             if (p[j] != p[k])
30                 next[j] = k;   //之前只有这一行  
31             else
32                 //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
33                 next[j] = next[k];
34         }
35         else
36         {
37             k = next[k];
38         }
39     }
40     int ans = 0;
41     int m = t.size();
42     for (int i = 0, j = 0; i<m; i++){
43         if (j < pLen && t[i] == p[j])  j++;
44         else{
45             while (j > 0){
46                 j = next[j];
47                 if (t[i] == p[j]){
48                     j++;
49                     break;
50                 }
51             }
52         }
53         if (j == pLen)     ans++;
54     }
55     return ans;
56 }
57 
58 int main(){
59     //    freopen("in.txt", "r", stdin);
60     string t, p;
61     int n;
62     scanf("%d", &n);
63     while (n--){
64         cin >> p >> t;
65         cout << KMP(t, p) << endl;
66     }
67     return 0;
68 }

View Code

三、NEXT数组

1.什么是NEXT数组

next数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next[j] = k，代表j之前的字符串中有最大长度为k的相同前缀后缀。

2.如何求解

* 如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。
此意味着什么呢？究其本质，next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。

* 下面的问题是：已知next [0, ..., j]，如何求出next [j + 1]呢？对于P的前j+1个序列字符：
若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。

3.优化

当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。

参考文献
1.JULY《从头到尾彻底理解KMP》