leetcode字符串匹配算法之KMP算法

本篇介绍一种高效的字符串匹配算法——KMP算法。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出，取三个人名字的第一个字母，简称KMP算法。KMP的核心思想就是在某次匹配失败的时候，利用已经匹配的成功的字符串的信息——称之为部分匹配表，来减少模式串和主串的匹配次数，因此KMP算法很高效，的时间复杂度O(m+n)。

从上面的介绍可以看出，KMP的核心就是要利用好已经匹配的信息，避免重复匹配，关键就在于如何得到“部分匹配表”，要理解这一过程，我们一步一步来分解下字符串的匹配过程。假设我们需要在字符串BDABCDABCEABCDABCSF（主串）中来查找ABCDABCSF（模式串）

• 从主串的第一个字符和模式串的第一个字符开始对比是否相等

• 第一个字符不相等，继续往后移动：第一次匹配到的位置

• 继续匹配，直到匹配不成功：主串字符E与模式串字符S不相等

• 这个时候常规的做法回到模式串的第一个字符（A），从主串的下一个字符（B）开始重新匹配

• KMP算法此时的特殊性体现出来了，它并不回退到模式串的第一个字符重新开始匹配，而是利用已经匹配过的信息，很显然我们可以看到，模式串开头的字符"ABC"在匹配失败的字符“S”前面又出现了。意味着什么？意味着“ABC”在“S”前面的位置也匹配成功了，也就是说下一个能成功匹配模式串开头的位置应该是在“S”前面的位置，可以直接把模式串开头的“ABC”移动到原来“S”前面的位置，并从模式串的第4个字符“D”开始重新匹配！

• 正是因为字符"S"前的"ABC"是对模式字符串起始位置的重复，意味着移动到该位置肯定可以匹配模式字符串的前3个字符（也就是"ABC"），并且移动到该位置之前的位置，模式字符串肯定不能匹配成功。这个现象的实质是：模式字符串匹配失败的字符（示例中的"S"）往前的字符都是匹配成功的（示例中的"ABCDABC"），为了方便，我们叫它匹配成功子串，匹配成功子串的头部和尾部有时候会存在重复（“ABC”重复了），尾部的匹配也就意味着头部的匹配，因此可以利用这个尾部匹配的信息，直接移动模式字符串头部到匹配成功子串尾部的位置！并且匹配成功子串的头部和尾部重复长度是其前缀集合和后缀集合中相同子串的最长长度，参见Jake Boxer的文章。

• 这个最长长度就是前文提到的部分匹配表，部分匹配表对应的是模式字符串每个位置的部分匹配值，匹配失败时，模式字符串能移动的位置即为：匹配成功子串的长度-匹配成功子串的尾部字符的部分匹配值；它是针对模式字符串而言。还是以模式字符串"ABCDABCSF"为例，来计算部分匹配表。

• "A"的部分匹配值是0，因为"A"没有前缀和后缀（头尾字符除外的后缀和前缀），"AB"的部分匹配值是0（前缀和后缀分别为"A"、"B"，相同子串最长长度为0），以此类推，"ABCDAB"的部分匹配值是2（最长相同的前后缀长度为2，也就是"AB"），"ABCDABC"的部分匹配值是3，"ABCDABCS"的部分匹配值是0，"ABCDABCSF"的部分匹配值是0。因此整个模式字符串的部分匹配表如下：

字符	A	B	C	D	A	B	C	S	F
索引	0	1	2	3	4	5	6	7	8
部分匹配值	0	0	0	0	1	2	3	0	0

• 有了这个表之后，一旦匹配不成功，我们就可以根据部分匹配值来计算模式字符串移动的距离，以及重新开始匹配的字符位置。假设模式字符串个数为n，用pattern[n]表示，部分匹配表用next[n]表示，当前成功匹配子串长度为K，那么：

模式字符串移动的距离 = K - next[K - 1]

重新开始匹配的字符位置 = K，也就是从pattern[K]开始与主串匹配

部分匹配表和KMP算法的实现

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

void printPMT(const char *pattern, int *next, int len) {
    printf("------Partial Match Table--------\n");
    for (int i = 0; i < len; i++) {
        printf("%c ", pattern[i]);
    }
    printf("\n");

    for (int i = 0; i < len; i++) {
        printf("%d ", next[i]);
    }
    printf("\n");
    printf("----------------------------------\n");
}

void next(const char *pattern, int *next, int len) {
    for (int i = 0; i < len; i++) {
        next[i] = 0;
        for (int preIndex = i; preIndex > 0;) {
            if (pattern[next[preIndex - 1]] == pattern[i]) {
                next[i] = next[preIndex - 1] + 1;
                break;
            }
            preIndex = next[preIndex - 1];
        }
    }

    printPMT(pattern, next, len);
}

int kmp_match(const char *str, const char *pattern) {
    if (str == NULL || *str == 0 || pattern == NULL || *pattern == 0) {
        return -1;
    }
    
    int lenOfPattern = strlen(pattern);
    int *nextTbl = (int *)malloc(lenOfPattern * sizeof(int));
    if (nextTbl == NULL) {
        return -1;
    }
    memset(nextTbl, 0, lenOfPattern * sizeof(int));
    next(pattern, nextTbl, lenOfPattern);

    int matchIndexOfMainString = 0;
    int matchStartIndexOfMainString = 0;
    int matchIndexOfPatternString = 0;
    int lenOfMainString = strlen(str);
    while (true) {  
        for (; matchIndexOfMainString < lenOfMainString && matchIndexOfPatternString < lenOfPattern; matchIndexOfMainString++, matchIndexOfPatternString++) {
            if (str[matchIndexOfMainString] != pattern[matchIndexOfPatternString]) {
                break;
            }
        }

        if (matchIndexOfPatternString == lenOfPattern) {
            free(nextTbl);
            return matchStartIndexOfMainString;
        }

        if (matchIndexOfMainString == lenOfMainString) {
            free(nextTbl);
            return -1;
        }
        
        if (matchIndexOfPatternString == 0) {
            matchStartIndexOfMainString += 1;
            matchIndexOfMainString = matchStartIndexOfMainString;
        } else {
            matchStartIndexOfMainString += matchIndexOfPatternString - nextTbl[matchIndexOfPatternString - 1];
            matchIndexOfPatternString = nextTbl[matchIndexOfPatternString - 1];
        }

    }
    free(nextTbl);

    return -1;
}

char *myStrstr(char *str, char *pattern) {
    int pos = kmp_match(str, pattern);
    if (pos >= 0) {
        return &str[pos];
    }
    return NULL;
}

int main(int argc, char **argv) {
    const char *str = "aaaaabaa";
    const char *pattern = "aabaa";
    int pos = kmp_match(str, pattern);
    if (pos >= 0) {
        printf("Find %s in pos %d\n", pattern, pos);
    } else {
        printf("Match failed!\n");
    }

    return 0;
}