嵌入式算法15-KMP字符匹配算法

摘要：改进的字符串匹配算法–KMP算法

1、问题

嵌入式软件开发时会在某个长字符串中，检索出现指定字符串标识的需求，最常用的库函数就是strstr。其源码有很多版本，常用经典实现方式：

char *strstr(const char *str1, const char *str2) {
    char *cp = (char *) str1;
    char *s1, *s2;
    if (!*str2)
        return ((char *) str1);
    while (*cp) {
        s1 = cp;
        s2 = (char *) str2;
        while (*s1 && *s2 && !(*s1 - *s2))
            s1++, s2++;
        if (!*s2)
            return (cp);
        cp++;
    }
    return NULL;
}

所有以str开头的字符串处理函数，最大限制是对传入的指针内容，中间不能出现‘\0’，否则会导致字符串截止。上面的源码中出现的3处条件判断，只对ASCII码字符串有效。

实际应用中，从一个大数组中找出小数组出现的位置，两个数组的内容可能出现0x00，使用strstr就无法满足需求。

2、暴力查找

根据查找需求，不难实现暴力查找算法，在主串中逐个查找子串第一个数据，相等则匹配第二个；出现不相同的则主串位置回到第一次相等位置加1，而子串回到第一个位置重新开始匹配。

#include "string.h"
#include "stdio.h"

typedef unsigned char uint8_t;

/**
 * @brief brute_force 字符串暴力匹配算法
 * @param str 主串数据
 * @param str_size
 * @param sub 模式串数据，需匹配的关键字数据
 * @param sub_size
 * @return
 *    <0 :fail
 *    >=0 :success ,sub在str中出现地址的偏移量
 */
static int brute_force(const uint8_t *str, int str_size,const uint8_t *sub,int sub_size)
{
    int i = 0;
    int j = 0;

    if(sub_size==0)
    {
        return 0;
    }

    if(str_size < sub_size)
    {
        return -1;
    }

    while(i < str_size && (j < sub_size))
    {
        if(str[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i-j+1;
            j = 0;
        }
    }

    if(j == sub_size)
    {
        return i - j;
    }
    else
    {
        return -1;
    }
}

int main(int argc, char *argv[])
{
    int ret;

    uint8_t str[]={0x00,0x11,0x00,0x11,0x33,\
                   0x00,0x11,0x00,0x11,0x44,\
                   0x00,0x11,0x00,0x11,0x22,\
                   0x00};
    uint8_t sub[]={0x00,0x11,0x00,0x11,0x22};

    ret=brute_force(str,sizeof(str),sub,sizeof(sub));
    printf("ret=%d\r\n",ret);

    return 0;
}

//运行结果
ret=10

从上面的暴力查找算法，sub出现在str主串的地址偏移10字节的地方，功能是正常，但效率呢？2次出现比较到最后一个字节才出现不相同，然后重新开始查找，是否可以改进呢？

在字串（模式串）中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串和模式串地址都需要回退，这就损失了效率。

分析sub子串，其前部分有重复的0x00 0x11,如果在0x22处比较不同，是不需要回退，可以只是回退1个字节继续比较，这样提高检索效率。这个思路，就是本文重点KMP算法。

3、KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串（子串）与主串的匹配次数，以达到快速匹配的目的。

以下数据是16进制，就是为了表明KMP支持任意值的数组查找，不限ASCII。

假设已经查找到中间某个状态，如下表：

使用暴力查找，下一步比较的效果如下：

而使用KMP可以越过前面的：

数组下标不用回退，继续往前移动比较，效率明显比暴力查找快。

对于KMP中模式串比较如何偏移，需要在检索前根据模式串的前缀生成next数组。

完整KMP算法如下：

//自动重建偏移关系表
int *get_next(const uint8_t *str1, int length, int *next)
{
    int i, j;
    i = 0;
    j = -1;
    next[0] = -1;
    while(i < length)
    {
        if(j == -1 || str1[i] == str1[j])
        {
            ++i;
            ++j;
            if(str1[i] != str1[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}

/**
 * @brief brute_force
 * @copyright  微信公众号【嵌入式系统】
 * @param str 主检索数据
 * @param str_size
 * @param sub 需匹配的关键字数据
 * @param sub_size
 * @return
 *    <0 :fail
 *    >=0 :success ,sub在str中出现的地址偏移量
 */
int kmp(const uint8_t *str, int str_size, const uint8_t *sub, int sub_size)
{
    int i = 0;
    int j = 0;
    int next[1025];//大于sub_size

    get_next(sub, sub_size, next);
    while(i <= str_size &&  j <= sub_size)
    {
        if(j == -1 || str[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j >= sub_size)   //返回值为第一次匹配到该字符串的位置
    {
        return i - sub_size -1;//第i个，但从0开始计算下标，需要减1
    }
    else
    {
        return -1;
    }
}

4、对比

为验证三种查找算法的效率，定义较长的两ASCII字符串，运行10000次，其时间如下图：

KMP的算法明显占优，因为模式串中有循环出现的片段，这种更能体现KMP的效率。

对于不同场景的算法选择，可参考下面的方式：

if (主串和模式串内容都是ASCII串)
{
    if(两字符串都比较简短)
    {
        strstr
    }
    else
    {
        strstr or kmp //子串有大量重复片段的更能体现效率，如 ABCDABCDABCDE，否则差不多
    }
}
else
{
    if(两字符串都比较简短)
    {
        暴力 or kmp  //如果子串前面没有重复片段，而且长度小于255，暴力算法不一定差
    }
    else
    {
        kmp
    }
}