Kmp算法我是看July博客学习，这里只是做个笔记，详细内容见July的blog:
http://blog.csdn.net/v_july_v/article/details/7041827
Kmp算法的用途：有一个文本串S和一个模式串P,现在要查找P在S中的位置。暴力匹配算法需要对文本串S进行回溯，kmp算法就是让文本串不回退，只需要移动模式串j即可。
Kmp算法大体思想：就是当s[i]==p[j]时，我们对i++，j++；如果不相等则令j=next[j]。这里next[j]为j字符之前的字符串中有多大长度的相同前缀后缀（注意前缀不能包含最后一个，同时后缀不能包含第一个，所以aaaab的next数组为-10123）。相当于将模式串向右移动了j-next[j]位。Next数组的求解采用的是迭代的思想，需要分p[j]是否等于p[k]两种情况以求得next[j+1]。
时间复杂度：暴力匹配算法的时间复杂度为O(n*m)(最差的情况). Kmp算法的时间复杂度为O(n+m)， 因为match串(模式串)最多向右推动了长度就为n,而字符串本身不回退。这里n和m分别为文本串和字符串的长度。next时间复杂度为O(M)，可以这样理解：循环中有两个变量，j和k,而j与j-k每次都是增加的或者一个不变，故最多循环2M次，时间复杂度为O(M)
Next数组求解：next[0]=-1，k=-1; next数组通过代码递推求得，假定next[j] = k求next[j+1]，先判断p[j]是否等于p[k], 如果相等则令next[++j] =++k; 否则令k=next[k]<这个不太好理解>继续迭代。时间复杂度为O(m).
k=next[k]；为什么不是k--？给个例子DADCDADDE, 当求E的next值时就会出错。k=k-1的话求到的是倒数第二个D，则为next[E]=2+1=3这里是DAD明显不对，然后再看ABDABCABDABDE据对称性得k=next[k]是正确的
优化next数组：next数组主要针对模式串abab的情况，比如在文本串abacab中寻找，此时当p[3]与s[3]匹配失败时，则将abab向右移动两位，此时p[1]仍然等于b，匹配必然失败，优化的next数组主要解决这个问题。当p[3]=p[next[3]]时 令next[3]=next[next[3]]。看代码则很好理解了。
以上则是个人理解笔记，下面给出具体代码：
1：kmp算法代码
#include <iostream>
using namespace std;
// 获取next数组
void getNext(int *next, const char *p) // 已知next[j] 求next[j+1] 分p[j]是否等于p[k]两种情况 迭代的思想
{
next[0] = -1;
int k = -1;
int j = 0;
while(j < strlen(p)-1)
{
if(k == -1 || p[j] == p[k])
{
k++;
j++;
next[j] = k;
}
else{
k = next[k]; // 继续迭代
}
}
}
// 获取优化next数组
void getNextOpt(int *next, const char *p) // 已知next[j] 求next[j+1] 分p[j]是否等于p[k]两种情况 迭代的思想
{
next[0] = -1;
int k = -1;
int j = 0;
while(j < strlen(p)-1)
{
if(k == -1 || p[j] == p[k])
{
k++;
j++;
if(p[j] != p[k]) // 对next数组进行优化 以对abab 这样的不需要进行重复
next[j] = k;
else next[j] = next[k];
}
else{
k = next[k]; //
}
}
}
// kmp 算法
int kmpSearch(const char *p, const char*s)
{
int ptrLen = strlen(p); // 获取模式串和文本串的长度
int strLen = strlen(s);
int *next = new int[ptrLen]; // 动态申请next数组
getNext(next, p); // 获取next数组
int i = 0, j = 0;
while(i < strLen && j < ptrLen){
if(j == -1 || s[i] == p[j])
{
i++;
j++;
}
else if(j == 0) // 这样对于首字符不满足的时候直接优化
i++;
else{
j = next[j];
}
}
delete[] next; // 释放动态申请的数组
if(j == ptrLen)
return i - j;
else return -1;
}
int main(){
char *ptr = "abcd";
char *str = "abababcd";
cout << kmpSearch(ptr, str) << endl;
return 0;
}
2：暴力匹配算法——又被称为朴素字符串匹配算法(Naive string match)
#include <iostream>
using namespace std;
int violenceSearch(const char *p, const char *s)
{
int ptrLen = strlen(p); // 获取模式串和文本串的长度
int strLen = strlen(s);
int i = 0, j = 0;
while(i < strLen && j < ptrLen){
if(s[i] == p[j])
{
i++;
j++;
}
else{
i = i-j+1;
j = 0;
}
}
if(j == ptrLen)
return i - j;
else return -1;
}
int main(){
char ptr[100];
char str[100];
cin >> ptr >> str;
cout << violenceSearch(ptr, str) << endl;
}
3：求最大长度表算法
也可以由最大长度表来求next数组，通过最大长度表各项向右移动一位，然后初值赋值-1即可，但是这种方法求最大长度表所消耗的时间为O(n^2)
// 针对一个字符串获得最大长度的相同前缀后缀
int getMaxFix(const char *p, int pLen)
{
int k =pLen/2;
while(k > 0)
{
//bool flag = false;
int i = 0, j = pLen -k;
while(i < k)
{
if(p[i] == p[j])
{
i++;
j++;
}
else{
//flag = true;
k--;
break;
}
}
}
return k;
}
// 获得最大长度表
void getMaxTable(const char *p, int *table)
{
for(int i = 0; i < strlen(p); i++)
{
table[i] = getMaxFix(p, i+1);
}
}
KMP算法的变形
这是hihoCoder1015的题目。题目地址：http://hihocoder.com/problemset/problem/1015
即求模式串在文本串中出现的次数。这里算法的基本思想就是求出模式串的公共前缀后缀即next[s.size()]，当j==s.size()的时候让j=next[s.size()]就可以了。就好比模式串ABCDEA，当结束的时候j=6，此时next[j] = 1,故让j=1继续去匹配，即前面有k位和字符串中是相同的。
代码如下：
#include <iostream>
#include <string>
using namespace std;
#define PMAXSIZE 10010
void getNext(int *iNext, const string s){
int j = 0, k = -1;
iNext[0] = -1;
string p = s+"#";
while(j < p.size()-1){
if(k == -1 || p[j] == p[k]){
j++;
k++;
if(p[j] != p[k])iNext[j] = k;
else iNext[j] = iNext[k];
}
else k = iNext[k];
}
}
int kmpAlg(const string &p, const string &s){
int i = 0, j = 0;
int count = 0;
int *iNext = new int[p.size()+1];
getNext(iNext, p);
while(i < s.size()){
if(j == -1 || s[i] == p[j]){
i++;
j++;
}else if(j == 0)
i++;
else
j = iNext[j];
if(j == p.size()){
count++;
j = iNext[j];
}
}
delete []iNext;
return count;
}
/*
//freopen是被包含于C标准库头文件<stdio.h>中的一个函数，用于重定向输入输出流。
该函数可以在不改变代码原貌的情况下改变输入输出环境，但使用时应当保证流是可靠的。
*/
int main(){
int N;
#define KMP1015
#ifndef KMP1015
freopen("input.txt", "r", stdin);
#endif
cin >> N;
while(N--){
string p, s;
cin >> p >> s;
cout << kmpAlg(p, s) << endl;
}
return 0;
}
/*
input:
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
output:
3
1
3
1
0
*/
参考文献：http://blog.csdn.net/v_july_v/article/details/7041827
作者：小村长 出处：http://blog.csdn.net/lu597203933 欢迎转载或分享，但请务必声明文章出处。
（新浪微博：小村长zack, 欢迎交流！