简介

KMP算法是对BF算法的改进和升级。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串（子串）与主串的匹配次数，以达到快速匹配的目的。
原理:每趟匹配过程中出现字符比较不相等时，不回溯指针，利用已得到的“部分匹配”结果将模式串向右滑动尽可能远一段的距离，然后继续进行比较。

实现

概念补充

前缀:除了最后一个字符外，一个字符串的全部头部组合。
后缀:除了第一个字符外，一个字符串的全部尾部组合。
最大共有长度（部分匹配值）：前缀和后缀中相同的组合中最大的一个组合的字符个数。

示例

实现步骤

1. 在KMP算法中，i(主串下标)不会先前移动(回溯)，需要移动的是j(子串下标)，所以我们需要知道j应该如何进行移动。
2. 在代码实现过程中，子串下标有如下关系:

j(表示子串下标)移动后的位置 = 模式串T的起始位置 + 部分匹配值
通常起始位置为0，所以
j(表示子串下标)移动后的位置 = 部分匹配值
j = next[j] , next[j]就是部分匹配函数，j为失配时的位置

所以我们需要另写一个函数Get_Next()来初始化next。以子串"aaaac"为例，具体过程如下:

代码

#include <stdio.h>
#include <string.h>

#define MAXSIZE 255

//KMP算法实现
int KMP(char * parent, char * child, int pos);
/** 部分匹配函数 */
void Get_Next(const char * child,int cLen,int * next);

int main() {
    char * str1 = "--hello123---";
    char  * str2 = "he";
    printf("\"%s\"在\"%s\"中第一次出现的位置为:%d\n",str1,str2,KMP(str1,str2,1));
    return 0;
}

int KMP(char * parent, char * child, int pos)
{
    //部分匹配表
   int next[MAXSIZE];
   //记录主串下标
   int i = pos;
   //子串的起始位置
   int j = 0;
   //主串长度
   int  pLen = strlen(parent);
   //子串长度
   int  cLen = strlen(child);

   //获取部分匹配表
   Get_Next(child,cLen,next);
   while (i < pLen && j < cLen)
   {
       if(j == 0 || parent[i] == child[j])
       {
           ++i;
           ++j;
       } else
       {
           //i不变，j后退（核心部分）
           j = next[j];
       }
   }
   if(j == cLen)
   {
       return (i + 1) - j;
   }
   return 0;
}

void Get_Next(const char * child,int cLen,int * next)
{
    //next的下标
    int i = 0;
    int j = -1;
    //此位置的值不会被用到
    next[0] = -1;

    while (i < cLen)
    {
        if(j == -1 || child[i] == child[j])
        {
            ++i;
            ++j;
            next[i] = j;
        } else{
            j = next[j];
        }
    }

}

运行截图

本文由 giao创作， 采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
原文地址：《KMP算法简要讲解和实现》