2014
02-19

# 常用算法-KMP匹配算法(2)优化

next[0]=0 的初始化在下面的计算中并不方便，大多数算法都是初始化 next[0] = -1; 而且只有next[0]为-1，其他next[i] >= 0.

//常规写法，求next数组的值
void getNext()
{
int i = 0; //pattern串的下标
int j = -1; //
next[0] = -1;
while (i < pattern_len - 1)
{
if (j == -1 || pattern[i] == pattern[j])
{
++i;
++j;
next[i] = next[j];
}
else
j = next[j];
}
}

//优化算法，求next数组的值
void getNext2()
{
int i = 0; //pattern串的下标
int j = -1; //
next[0] = -1;
while (i < pattern_len - 1)
{

if (j == -1 || pattern[i] == pattern[j])
{
++i;
++j;
if (pattern[i] != pattern[j]) //正常情况
next[i] = j;
else //特殊情况，这里即为优化之处。考虑下AAAAB, 防止4个A形成0123在匹配时多次迭代。
next[i] = next[j];
}
else
j = next[j];
}
}

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int next[100], pattern_len, str_len;
char * pattern, * str;

//优化算法，求next数组的值
void getNext2()
{
int i = 0; //pattern串的下标
int j = -1; //
next[0] = -1;
while (i < pattern_len - 1)
{

if (j == -1 || pattern[i] == pattern[j])
{
++i;
++j;
if (pattern[i] != pattern[j]) //正常情况
next[i] = j;
else //特殊情况，这里即为优化之处。考虑下AAAAB, 防止4个A形成0123在匹配时多次迭代。
next[i] = next[j];
}
else
j = next[j];
}
}

//求next数组的值
void getNext()
{
int i = 0; //pattern串的下标
int j = -1; //
next[0] = -1;
while (i < pattern_len - 1)
{
if (j == -1 || pattern[i] == pattern[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}

int kmp()
{
int i = 0, j = 0;
str_len = strlen(str);
getNext2(); // getNext();
while (i < str_len && j < pattern_len)
{
if (j == -1 || str[i] == pattern[j])
{
++i;
++j;
}
else
j = next[j];
}
if (j >= pattern_len)
return i - pattern_len;
else
return -1;
}

void printNext() {
for (int i = 0; i < pattern_len; i++)
cout << next[i] << " ";
cout << endl;

}

void getnext3(){
int i=0;
int j= next[0] = -1;
while( i < pattern_len){
if( j==-1 || pattern[i] == pattern[j] ){
i++; j++;
next[i] = j;
}else
j = next[j];
}
}

int main()
{
str = "AAAABAAACABAA";
pattern = "AAACAB";
pattern_len = strlen(pattern);
int res = kmp();
cout << res << endl;
printNext();

}

1. 常见算法是直接按照思路写了就放上来的吧，明显next ==next ,存在问题，而优化的那条，我直接拿过来，带入代码，也是错的

2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience