字符串的模式匹配算法

求子串位置的定位函数index

子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一。
一个最简单的匹配方法是：
从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。

匹配字符串
初始化：

之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：
比较字符是否一致
A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：把i指针移回第1位重新开始查找
算法实现如下：

int indexSubStr(MyString *S,MyString *substr,int pos){
    int i = pos,j = 0;
    while(i < S->length && j < substr->length){
        if(*(S->str + i) == *(substr->str + j)){
            i++; 
            j++; 
        }else{
            i = i - j + 1;
            j = 0;
        }
    }
    if(j == substr->length){
        return i - j;
    }else{
        return -1;
    }
}

上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也较高。较好的情况下，此算法的时间复杂度为O(n+m)。然而在有些情况下，该算法的效率却很低。例如，当模式串为“00000001”，而主串为“00000000000000000000000000000001”时，每趟比较都在模式的最后一个字符出现不等，此时需要将指针i重新回溯到i-6的位置上，并从模式的第一个字符开始重新比较，则最坏的情况下的时间复杂度为O(n*m)。

模式匹配的一种改进算法——KMP算法

这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

其改进在于：每一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的部分匹配的结果，将模式串向右滑动尽可能远的一段距离后，继续进行比较。
如：
比较字符发现不一致
此时，移动j到一个合适的位置k继续比较：

如下图也是一样的情况：

此时，移动j到一个合适的位置k继续比较：

至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。如下图所示：

下面讨论一般情况。假设主串为“s1s2….sn”,模式串为“p1p2…pm”,从上例的分析可知，为了实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即si≠pj）时，模式串“向右滑动”可行的距离多远，换句话说，当主串中第i个字符与模式中第j个字符“失配”时，主串中第i个字符（i指针不回溯）应与模式串中哪个字符再比较？

假设此时应与模式中第k（k<j）个字符继续比较，则模式中前k-1个字符的子串必须满足下列关系式，且不可能存在k’>k满足下列关系式：
“p1 p2 … pk-1” = “si-k+1 si-k+2 … si-1”
即下图蓝框圈起的上下两部分：

而已经得到的部分匹配的结果是：
“pj-k+1 pj-k+2 … pj-1” = “si-k+1 si-k+2 … si-1”
即下图蓝框圈起的上下两部分：

那么可以推得下列等式：
“p1 p2 … pk-1” = “pj-k+1 pj-k+2 … pj-1” 。
即下图表示的两边相等的部分：
k两边相等的部分

即，若模式中存在满足上式的两个子串，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式串向右滑动至模式中第k个字符和主串中第i个字符对齐，此时，模式中前k-1个字符的子串“p1 p2 … pk-1”必定与主串中第i个字符之前长度为k-1的子串“si-k+1 si-k+2 … si-1”相等，由此，匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。

因为在p的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当s[i] != p[j]时，j指针的下一个位置。由此可引出模式串的next函数的定义：

next[j]=	-1	当j = 0时
	Max{k丨0<k<j且“p0 p1 … pk-1” = “pj-k pj-k+1 … pj-1”}	当此集合不空时
	0	其他情况

求得模式串的next函数之后，匹配可如下进行：
假设以指针i和j分别指示主串和模式中正待比较的字符，令i的初值为pos，j的初值为0。
若在匹配的过程中s[i]=p[j]，则i，j分别增1，继续比较；
若s[i]≠p[j]，则i不变，而j退到next[j]的位置再比较，若相等，则指针各自增1，否则j再退到next[j]的位置再比较，以此类推；
若j退到值为0，则此时需将模式串继续向右滑动一个位置，即从主串的下一个字符si+1起和模式串重新开始匹配。

KMP算法实现如下：

int myStringIndexSubString(MyString *S,MyString *substr,int pos){ //KMP算法
    int i = pos,j = 0;
    if(!S || !substr || pos > S->length) return -1;
    int *nextval = getKMPNext(substr);
    if(!nextval) return -1;
    while(i < S->length && j < substr->length){
        if(*(S->str + i) == *(substr->str + j)){
            i++; 
            j++; 
        }else{
            j = *(nextval+j); //i不需要回溯，j回到指定位置
            if(j == -1){
                i++; //当j为-1时，要移动的是i
                j++; //j归0
            }
        }
    }
    free(nextval);
    if(j == substr->length){
        return i - j;
    }else{
        return -1;
    }
}

KMP的算法是在已知模式串的next函数值的基础上执行的，那么，如何求得模式串的next函数值是很重要的。
从上述讨论可见，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可以从分析其定义出发用递推的方法求得next函数值。

先来看第一个：当j为0时，如果这时候不匹配，怎么办？
当j为0时就不匹配
像上图这种情况，j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next[0] = -1这个初始化。如果是当j为1的时候呢？
当j为1的时候不匹配
显然，j指针一定是后移到0位置的。因为它前面也就只有这一个位置了，next[1] =0。

当{0<k<j且“p0 p1 … pk-1” = “pj-k pj-k+1 … pj-1”}集合不空时，设next[j] = k,这表明在模式串中存在下列关系：
“p0 p1 … pk-1” = “pj-k pj-k+1 … pj-1”，其中k为满足0<k<j的某个值，并且不可能存在k’>k满足前面的等式。
此时next[j+1] =？可能有两种情况：
1.p[k] = p[j],如下图所示：

前面next[j] = k时，已经存在“p0 p1 … pk-1” = “pj-k pj-k+1 … pj-1”这一等式，若p[k] = p[j]，则很容易的得出：
“p0 p1 … pk” = “pj-k pj-k+1 … pj”，
即在此基础上两边加上相等的p[k]、 p[j]，
则next[j+1] = k+1，即next[j+1]=next[j] +1。

2.p[k] != p[j]，如下图所示：

此时“p0 p1 … pk” != “pj-k pj-k+1 … pj”，可以把求next函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而当前在匹配过程中，已有“p0 p1 … pk-1” = “pj-k pj-k+1 … pj-1”这一等式，则当p[k] != p[j]时应将模式串向右滑动至以模式串中的第next[k]个字符和主串中的第j个字符相比较，如下图所示：

这就是为什么代码中为k = *(nextval+k)

当其他情况时，next[j] =0，这表明模式串从头开始比较。

getKMPNext函数

static int *getKMPNext(MyString *substr){
    int *nextval = (int *)malloc((substr->length)*sizeof(int));
    int j=0,k=-1;
    if(nextval){
        *nextval = -1;
        while(j<substr->length){
            if(k == -1 || *(substr->str+j) == *(substr->str+k)){
                if(*(substr->str+(++j)) == *(substr->str+(++k))){ //两个字符相等时跳过
                    *(nextval+j) = *(nextval+k);
                }else{
                    *(nextval+j) = k;
                }
            }else{
                k = *(nextval+k);
            }
        }
        return nextval;
    }else{
        return NULL;
    }
}

在上面的getKMPNext函数中还修正了next的值。前面定义的Next表达式有一个小缺陷，看一个例子：

显然，根据Next表达式得到的next数组应该是[ -1，0，0，1 ]，所以下一步我们应该是把j移动到第1个元素：

不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
发生问题的原因在于P[j] == P[next[j]]。
所以在getKMPNext函数中添加一个判断条件：

1	if((substr->str+(++j)) == (substr->str+(++k))){ //两个字符相等时跳过

修正后的next数组是[ -1，0，0，0 ]。

getKMPNext函数的时间复杂度为O(m)。通常，模式串的长度m比主串的长度n要小的多，因此，对整个匹配算法来说，所增加的这点时间是值得的。

最前面介绍的匹配算法的时间复杂度是O(n*m),但在一般情况下，其实际的执行时间近似于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下才显得比这个算法快得多。但是KMP算法的最大特点是指示主串的指针不需要回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。

KMP算法的实现基于之前的C封装字符串、字符串数组对象内容：C封装字符串、字符串数组对象

github源码

testMyString.c文件：

#include <stdio.h>
#include <malloc.h>
#include "MyString.h"

int printMyString(MyString *str){
    printf("%s, ",str->str);
    printf("length :%d\n",str->length);
    return 0;
}

int printMyStringElem(MyString **str){
    printf("%s ",(*str)->str);
    return 0;
}

int main(void){
    int i;
    char words[] = {"without new experiences, something inside of us sleeps."};
    MyString *str_a = NULL;
    MyString *str_b = NULL;
    MyString *str_c = NULL;
    MyStringArray *str_array = NULL;

    str_a = myStringAssign("hello ");
    str_c = myStringAssign("hello ");

    printf("str_a :");
    printMyString(str_a);

    printf("is MyString empty: %d\n",isMyStringEmpty(str_a));

    if(compareMyString(str_a,str_c)==0){
        printf("str_a equals str_c\n");
    }else{
        printf("str_a is not equal str_c\n");
    }

    clearMyString(str_a);

    printf("is MyString empty: %d\n",isMyStringEmpty(str_a));

    if(compareMyString(str_a,str_c)==0){
        printf("str_a equals str_c\n");
    }else{
        printf("str_a is not equal str_c\n");
    }

    destroyMyString(str_a);
    str_a = copyMyString(str_c);
    

    str_b = myStringAssign("Mr Bluyee");
    printf("str_b :");
    printMyString(str_b);

    destroyMyString(str_c);
    str_c = concatMyString(str_a,str_b);
    printf("str_c :");
    printMyString(str_c);
    
    printf("the MyString : Mr Bluyee index: ");
    i = myStringIndexSubString(str_c,str_b,0);
    printf("%d\n", i);
    
    printf("the char \'B\' index: %d\n", myStringIndexChar(str_c,'B',0));

    insertMyString(str_a,str_b,str_a->length);
    printf("str_a :");
    printMyString(str_a);

    destroyMyString(str_c);
    str_c = substrMyString(str_a,0,5);
    printf("str_c :");
    printMyString(str_c);

    destroyMyString(str_c);
    str_c = myStringAssign(words);
    str_array = splitMyString(str_c,' ');
    str_array->traverse(str_array,printMyStringElem);

    destroyMyString(str_a);
    destroyMyString(str_b);
    destroyMyString(str_c);
    DestroyMyStringArray(str_array);
    return 0;
}

KMP匹配的调用的代码段是：

1
2
3

printf("the MyString : Mr Bluyee index: ");
i = myStringIndexSubString(str_c,str_b,0);
printf("%d\n", i);

编译：

1	gcc MyString.c MyString.h MyStringArray.c MyStringArray.h testMyString.c -o testMyString

运行testMyString：

str_a :hello , length :6
is MyString empty: 0
str_a equals str_c
is MyString empty: 1
str_a is not equal str_c
str_b :Mr Bluyee, length :9
str_c :hello Mr Bluyee, length :15
the MyString : Mr Bluyee index: 6
the char 'B' index: 9
str_a :hello Mr Bluyee, length :15
str_c :hello, length :5
without new experiences, something inside of us sleeps.

本篇文章部分内容整理自：（原创）详解KMP算法