问题： 用给定的模式P，在目标字符串T中搜索与模式P全同的一个子串，并求出T中的第一个和p全同匹配的子串。
方法一：朴素模式匹配
（穷举法），目标长度为n，模式长度m时，O（nm）
方法二：KMP
由于朴素模式匹配中存在很多冗余的计算，除掉这些冗余可以加速整个匹配时间，于是有了KMP算法。
例如： abcabefab 与 abe进行匹配，朴素在计算完abc与abe不匹配后，会继续计算b与a是否匹配，c与a是否匹配。
而KMP算法，是尽量找到出现不匹配点时，下一个应该开始计算的位置。如上例abc与abe不匹配后，可以直接计算c是否与a匹配。
KMP算法发现每次出现误配时，应该如何选择下一个要测试的点只跟模式P本身有关。
KMP算法计算字符串特征向量N：构造方法：
定义：模板P的前缀子串（P0 P1 ... P t-1）左子串 （Pi-t ... Pi-2 Pi-1）
计算模板p第j个位置的特征数ni：最长的 t 能够与前缀子串匹配的左子串 ，计算方式如下：
例如 a b c a a b a b c
next[] -1 0 0 -1 1 0 2 0 0
计算特征向量N的算法实现如下
int*Next(String P) { // 计算向量N
int m = P.size; // m为模板P的长度
assert( m > 0); // 若m＝0，退出
int *N = new int[m]; // 动态存储区开辟整数数组
assert( N != 0); // 若开辟存储区域失败，退出
N[0] = -1;
int i = 0;
int j = -1;
while (i < m) {
while (j >= 0 && P.str[i] != P.str[j])
j = N[j];
i++;
j++;
N[i] = j;
}
returnN;
}
KMP模式匹配算法实现：int KMP_FindPat(StringS, String P, int *N, int startindex) {
// 假定事先已经计算出P的特征数组N，作为输入参数
int LastIndex = S.size - P.size; // S末尾再倒数一个模板长度位置
if ((LastIndex - startindex) < 0)
return (-1); // startindex过大，匹配无法成功
int i; //i 是指向S内部字符的游标
int j = 0; // j 是指向P内部字符的游标
for (i = startindex; i < S.size; i++) { // S游标i循环加1
//若当前位置的字符不同，则用N循环求当前的j，用于将P的恰当位置与S的i位置对准
while (P.str[j] != S.str[i] && j > 0)
j =N[j];
if (P.str[j] == S.str[i]) // P[j]与S[i]相同，继续下一步循环
j++;
if ( j == P.size) // 匹配成功，返回该S子串的开始位置
return (i - j +1);
};
return (-1); // P和S整个匹配失败，函数返回值为负
}
KMP算法效率分析