字符串匹配算法——KMP算法
一、算法介绍：
KMP算法是一种改良的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因而人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的外围是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到疾速匹配的目标。
具体实现就是通过一个next()函数实现，函数自身蕴含了模式串的部分匹配信息。
二、算法具体分析：
1、写出字符串前缀；
2、找出每个前缀字符串的最长公共前后缀；
3、写出前缀表prefix table；
4、依据前缀表进行匹配。
三、例子：
T：a b a a c a b a b c a c
P：a b a b c
首先写出字符串P的前缀如下：
最长公共前后缀长度 前缀表a 0 -1
a b 0 0
a b a 1 0
a b a b 2 1
a b a b c 0 2
而后依据前缀表进行匹配：
T：a b a a c a b a b c a c
0 1 2 3 4 数组下标
P：a b a b c
-1 0 0 1 2 前缀表：当不匹配的时候将对应下标的字母挪动到以后比拟的地位。
过程：
T：a b a a c a b a b c a c
√ √ √ ×
0 1 2 3 4 数组下标
P：a b a b c
-1 0 0 1 2
此时a与b不匹配，能够看到前缀表里b所对应的是1，也就是将数组下标为1的字母b挪动到以后地位进行比拟如下：
T：a b a a c a b a b c a c
√ × 0 1 2 3 4 数组下标P：a b a b c -1 0 0 1 2 此时a和b还是不匹配，那么持续将下标为0的挪动到以后地位如下：
T：a b a a c a b a b c a c
√ × 0 1 2 3 4 数组下标 P：a b a b c -1 0 0 1 2 又不匹配继续移动：
T：a b a a c a b a b c a c
× 0 1 2 3 4 数组下标 P：a b a b c -1 0 0 1 2 不匹配继续移动：（-1的地位就是P串的a的后面一个地位，为空字符）
T：a b a a c a b a b c a c
√ √ √ √ √ —匹配胜利 0 1 2 3 4 数组下标 P：a b a b c -1 0 0 1 2 此时咱们匹配到了一个残缺的字符串，然而并没有完结，可能前面的字符串中还有可能匹配到的，所以此时继续移动，将下标为2的字符挪动到以后地位：
T：a b a a c a b a b c a c
0 1 2 3 4 数组下标 P：a b a b c -1 0 0 1 2 因为c和a不匹配所以咱们的匹配完结，不必持续往后比拟了，完结。
四、代码实现：
c++
include<iostream>
include<string.h>
using namespace std;
/*
pattern[]字符串
prefix[]前缀表
n字符串长度
*/
void prefix_table(char pattern[],int prefix[],int n) {
prefix[0] = 0;int len = 0;int i = 1;while (i<n) { if (pattern[i] == pattern[len]) { len++; prefix[i] = len; i++; } else { if (len > 0) { len = prefix[len - 1]; } else { prefix[i]= len; i++; } }}}
void move_prefix_table(int prefix[],int n) {
int i;for (i = n - 1; i > 0;i--) { prefix[i] = prefix[i-1];}prefix[0] = -1;}
void kmp_search(char text[],char pattern[],int p,int t) {
int n = p;int *prefix = (int*)malloc(n * sizeof(int));prefix_table(pattern,prefix,n);move_prefix_table(prefix,n);cout << "the prefix_table is ";for (int k = 0; k < n;k++) { cout << prefix[k]<<" ";}cout << endl;/*规定text[i] , len(text)=mpattern[j] , len(pattern)=n*/int i = 0;int j = 0;int m = t;while (i<m) { if (j == n - 1&&text[i]==pattern[j] ) { cout << "Found pattern,the position is " << i-j; j = prefix[j]; } if (text[i] == pattern[j]) { i++; j++; } else { j = prefix[j]; if (j==-1) { i++; j++; } }}}
int main() {
char pattern[] = "abba";char text[] = "abbbbabbcabbab";int p_len = strlen(pattern);int t_len = strlen(text);kmp_search(text,pattern, p_len, t_len);return 0;}