KMP算法是字符串模式匹配的一种经典算法。
设原串为s[]，模式串为p[]。
1. 朴素的算法
枚举匹配起始位置 i（s中），从起始位置 i 开始，与模式串中的字符逐次一一对比，直到匹配成功或者匹配失败， 然后++i，如此循环直到遍历完原串s。
2. KMP算法
2.1 出发点
对于某次匹配，如果第一个字符就没有匹配成功，那么跟朴素算法一样，将起始位置加1， 再继续做；但是，如果有一部分字符匹配成功了，我们是否可以利用这些匹配成功的子串信息？实际上利用这些信息我们可以做到两点优化，从而得到经典的KMP算法，具体见2.2.
2.2 KMP的核心思路
首先介绍两个概念：前缀和后缀。举例来说，对于字符串“ababa”, 它的前缀包括"a", "ab", "aba", "abab", 后缀包括"baba", "aba", "ba", "a"。
KMP的核心在于一个叫做next数组的东西，next数组中到底装的是什么呢？其实很简单，next[i]表示的是s[0...i]的前缀集合和后缀集合中最长的公共串的长度。在上面的例子“ababa”中，前缀集合和后缀集合中，公共串有两个，分别为长度为1的“a”和长度为3的“aba”，因此对应的next值为next[4] = 3（下标从0开始）。
有了next数组，我们就可以做到上面提到的两点优化了。
第一点优化：在枚举匹配起始位置的时候，每次移动的不再是1，而是移动到使得某个前缀和后缀相重合的位置，这里所提提到的某个前缀就是next值中所对应的那个公共串。如下所示：
| 下标 | 0 | 1 | 2 | 3 | 4 |
| 串 | a | b | a | b | a |
| next值 | 0 | 0 | 1 | 2 | 3 |
假设模式串为"aba", 匹配的步骤为（注意起始位置变化）：
(1) a b a b a
a b a
此时，匹配了前3个字符，于是起始位置向后移动3 - next[2] = 2， 而不是朴素匹配算法中的移动1.
(2)a b a b a
a b a
匹配结束。
第二点优化：在匹配的时候，不再是像朴素算法中那样每次从模式串中的第0个字符开始匹配，因为有了next数组，我们现在已经知道模式串中的一部分已经匹配了（next值的对应公共串），所以，就没必要再从第0个开始，而是从next值所对应的公共串的下一个字符开始。比如上面的步骤(2)， 不会再从模式串的第0个字符"a"开始与原串进行匹配，而是从第1个字符"b"开始。
2.3 next数组的求解步骤
(1) 显然next[0] = 0， 因为一个字符不具备任何前缀和后缀；
(2) 对于i>0, next[i]的计算：
令k = next[i-1]，此时我们已经知道p[0,...,k-1]==p[i-k,...i-1], 且p[0,...,k-1]就是p[0,...,i-1]的前后缀集合中的那个最长公共串。
如果p[i]==p[k]，那么显然有next[i] = k+1。
但当p[i]!=p[k]的时候我们该怎么办呢？此时next[i]的值显然不会超过k即next[i-1]，也就是说，这种情况下我们要找的那个公共串，要么不存 在，next[i]=0, 要么是next[i-1]对应的那个公共串的一个前缀，此时我们需要找到p[0,...,i-1]的一个较短的前后缀公共串，使得p[i]==p[k](k为所求较短公共 串的长度)，那么，我们该如何来找到上述那个较短的公共串呢？我们此时要找的那个较短公共串，是p[0,...i-1]的长度为k=next[i-1]的前缀的一个前缀和长度 为k=next[i-1]的后缀的一个后缀，而我们知道p[0,...i-1]中长度为k=next[i-1]的前缀和后缀是相同的，因此，我们找那个较短串的问题就转换为p[0,...,k-1] 的最长公共前后缀问题了，现在就可以用递归来求得那个较短串的长度。写成代码就一个简单循环:while(k!=0&&p[i]!=p[k]) k = next[k-1].
关于next数组求解的问题，我觉得这篇文章写的很好，比较容易懂，链接在此：http://blog.csdn.net/yearn520/article/details/6729426
最后，附上我的实现代码（题目来源：http://hihocoder.com/problemset/problem/1015）
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 #define MAX_PATTERN 10005 7 #define MAX_ORIGINAL 1000005 8 9 char pat_str[MAX_PATTERN]; 10 char ori_str[MAX_ORIGINAL]; 11 int next[MAX_PATTERN]; 12 13 void getNext() 14 { 15 int len = strlen(pat_str); 16 next[0] = 0; 17 for(int i=1; i<len; ++i) 18 { 19 int k = next[i-1]; 20 while(k!=0 && pat_str[i]!=pat_str[k]) 21 k = next[k-1]; 22 if(pat_str[i]==pat_str[k]) next[i] = k+1; 23 else next[i] = 0; 24 } 25 } 26 27 int kmp(char *s, char *p) 28 { 29 int cnt = 0; 30 int len_ori = strlen(ori_str); 31 int len_pat = strlen(pat_str); 32 getNext(); 33 int i = 0, j = 0; 34 for(int k=0; k<len_ori; ) 35 { 36 while(i<len_ori&&j<len_pat&&ori_str[i]==pat_str[j]) 37 { 38 ++i; 39 ++j; 40 } 41 if(j==len_pat) 42 { 43 ++cnt; 44 } 45 if(j==0) 46 { 47 ++k; 48 j = 0; 49 i = k; 50 } 51 else 52 { 53 k += j-next[j-1]; 54 i = k+next[j-1]; 55 j = next[j-1]; 56 } 57 } 58 return cnt; 59 } 60 61 int main() 62 { 63 int n; 64 scanf("%d", &n); 65 while(n--) 66 { 67 scanf("%s%s", pat_str, ori_str); 68 printf("%d ", kmp(ori_str, pat_str)); 69 } 70 71 return 0; 72 }