KMP算法

你好旅行者!欢迎来到cyt的练功房。本篇文章来记录一个我刚学会的算法KMP算法，主要用于字符匹配

先在开头约定，本文用 pat 表示模式串，长度为 M，txt 表示文本串，长度为 N。KMP 算法是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。

一、传统字符匹配

众所周知，传统的字符串匹配是一个O(N*M)的算法，在大多数的场合是过不了题的。大致如下

int search(string pat,string txt){
    # pat长度为M txt长度为N
    for(int i=0;i<=N-M;i++){
        int j;
        for(j=0;j<M;j++){
            if(!pat[j]==txt[i+j])break;
        }
        if(j==M)return true;
    }
    return false;
}

对于暴力算法，如果出现不匹配字符，同时回退 txt 和 pat 的指针，嵌套 for 循环，时间复杂度 O(MN)，空间复杂度O(1)。最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

KMP 算法的不同之处在于，它会花费空间来记录一些信息，只需要遍历一遍