【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

前面我们谈到了KMP算法，但是讲的还不是很详细。今天我们可以把这个问题讲的稍微详细一点。假设在字符串A中寻找字符串B，其中字符串B的长度为n，字符串A的长度远大于n，在此我们先忽略。

假设现在开始在字符串A中查找，并且假设双方在第p个字符的时候发现查找出错了，也就是下面的情况：

/*
* A: A1 A2 A3 A4 ... Ap ............
* B: B1 B2 B3 B4 ... Bp ...Bn
* (p)
*/
/*
* A: A1 A2 A3 A4 ... Ap ............
* B: B1 B2 B3 B4 ... Bp ...Bn
* (p)
*/

那么这时候，A有什么选择呢？它可以左移1位，用A2~A(p-1)比较B1~B(p-2)，然后再用A(p)~A(n+1)比较B(p-1)~B(n)位；或者左移2位，用A3~A(p-1)比较B1~B(p-3)，然后再用A(p)~A(n+2)比较B(p-2)~B(n)位； 依次类推，直到左移（p-2）位，用A(p-1)比较B(1)，然后再用A(p)~A(p+n-2)比较B(2)~B(n)位。

不知道细心的朋友们发现什么规律没？因为A和B在前面（p-1）个数据是相等的，所以上面的计算其实可以这样看：用A2~A(p-1)比较B1~B(p-2)，实际上就是B2~B(p-1)比较B1~B(p-2)； 用A3~A(p-1)比较B1~B(p-3)，实际上就是B3~B(p-1)比较B1~B(p-3)；最后直到B(p)和B(1)两者相比较。既然这些数据都是B自身的数据，所以当然我们可以提前把这些结果都算出来的。

那么这么多的选择，我们应该左移多少位呢？

其实判断很简单。假设我们左移1位，发现A2~A(p-1)的结果和B1~B(p-2)是一致的，那么两者可以直接从第(p-1)位开始比较了； 如果不成功呢，那么只能左移2位，并判断A2~A(p-1)和B1~B(p-2)的比较结果了，......，这样以此类推进行比较。如果不幸发现所有的数据都不能比较成功呢，那么只能从头再来，从第1位数据依次进行比较了。

不知道讲清楚了没，还没有明白的朋友可以看看下面的代码：

int calculate_for_special_index(char str[], int index)
{
int loop;
int value;

value = 0;
for(loop = 1; loop < index; loop ++){
if(!strncmp(&str[loop], str, (index - loop))){
value = index - loop;
break;
}
}

return (value == 0) 1 : (index - value);
}

void calculate_for_max_positon(char str[], int len, int data[])
{
int index;

for(index = 0; index < len; index++)
data[index] = calculate_for_special_index(str, index);
}
int calculate_for_special_index(char str[], int index)
{
int loop;
int value;

value = 0;
for(loop = 1; loop < index; loop ++){
if(!strncmp(&str[loop], str, (index - loop))){
value = index - loop;
break;
}
}

return (value == 0) 1 : (index - value);
}

void calculate_for_max_positon(char str[], int len, int data[])
{
int index;

for(index = 0; index < len; index++)
data[index] = calculate_for_special_index(str, index);
}

当然，上面当然都是为了计算在索引n比较失败的时候，判断此时字符应该向左移动多少位。

char* strstr_kmp(const char* str, char* data)
{
int index;
int len;
int value;
int* pData;

if(NULL == str || NULL == str)
return NULL;

len = strlen(data);
pData = (int*)malloc(len * sizeof(int));
memset(pData, 0, len * sizeof(int));
calculate_for_max_positon((char*)str, len, pData);

index = 0;
while(*str && ((int)strlen(str) >= len)){
for(; index < len; index ++){
if(str[index] != data[index])
break;
}

if(index == len){
free(pData);
return (char*) str;
}

value = pData[index];
str += value;

if(value == 1)
index = 0;
else
index = index -value;
}

free(pData);
return NULL;
}
char* strstr_kmp(const char* str, char* data)
{
int index;
int len;
int value;
int* pData;

if(NULL == str || NULL == str)
return NULL;

len = strlen(data);
pData = (int*)malloc(len * sizeof(int));
memset(pData, 0, len * sizeof(int));
calculate_for_max_positon((char*)str, len, pData);