比暴力匹配更温柔，比朴素更轻奢的KMP字符串匹配算法_C

KMP字符串匹配算法

一个人能能走的多远不在于他在顺境时能走的多快，
而在于他在逆境时多久能找到曾经的自己。

——KMP

看了《大话数据结构》以及《算法导论》书中对于KMP的讲解，只看的懂基本的思想，后面又去B站看了灯神和代码随想录的讲解视频，女少口阿！！！

对于KMP算法代码的具体细节理解还不够，下面先列出基本，过段时间后面能一遍过手撕出来的时候再结合自己的理解来完善。

(有时间的话手动狗头）

基本思想

先求出待匹配的子串到各位上字符的子串最长公共前缀的大小,所求得即为原生的最长公共前缀表。

之后在进行字符串一一匹配的时候，如果出现不匹配的情况，就可以利用这张表回退到之前上面已经匹配的部分的下一位来重新匹配。

因为有最长公共前缀，所以不匹配子串位置前面的前缀可以与父串的后缀进行匹配，而不用都跳到下一位重新开始匹配。

提高了时间效率。

LC28题ImplementStrstr——实现strStr() 题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。

如果不存在，则返回 -1 。

示例 1：

输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：

输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：

输入：haystack = “”, needle = “”
输出：0

KMP实现代码(cpp)

class Solution {
public:
//    static void prt(int val){
//        cout<
//    }

    int strStr(string haystack, string needle) {
        //前缀表
        vector<int>prefix;
        prefix.push_back(0);
        int i=1;
        int j=0;
        while (i<needle.size()){
            if(needle[i]==needle[j]){
                j++;
                prefix.push_back(j);
                i++;
            } else{
                if(j>0) {
                    j = prefix[j - 1];
                }
                else{
                    prefix.push_back(j);
                    i++;
                }
            }
        }
//        for_each(prefix.begin(), prefix.end(),prt);

        //移动前缀表
        i=needle.size()-1;
        while(i>0){
            prefix[i]= prefix[i-1];
            i--;
        }
        prefix[0]=-1;

        //kmp搜索
        i=0;
        j=0;
        while(i<haystack.size()){
            if(j==needle.size()-1&&haystack[i]==needle[j]){
                return i-j;
                //j= prefix[i];
            }
            if(haystack[i]==needle[j]){
                i++;
                j++;
            } else{
                j= prefix[j];
                if(j==-1){
                    i++;
                    j++;
                }
            }
        }
        return -1;
    }
};