KMP匹配字符串

题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/submissions/

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

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

示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

KMP思路简介

KMP的主要思想是：在匹配时，如果遇到某个项不匹配，则尝试利用之前已经匹配过的结果，避免从头继续匹配。对于字符串匹配，可以做到只遍历一遍文本串就匹配出结果。时间复杂度总暴力循环的O(m*n)降低到O(m+n)：匹配时间+生成Next数组的时间。

Next数组生成

next[i]表示：在模式串中，前i个（下标为0开始）字符组成的子串的 最长相同前后缀 的长度

• 最长相同前后缀：例：aabaa，最长相同前后缀为aa，长度为2。aabaab，最长相同前后缀为aab。

利用最长相同前后缀进行匹配：

例：文本串aabaabaafa，模式串aabaaf：

开始匹配，当文本串的第6个字符b和模式串的第6个字符f不匹配时，有：

1. b和f不匹配
2. b和f前面的字符是匹配的
3. 模式串中f前面的字符a的next数组数值为2即aabaa的最长相同前后缀长度为2
4. 模式串f的前两个字符aa = 文本串b的前两个字符aa = 模式串第0、第1个字符aa
5. 模式串的前两个字符已经和文本串b的前两个字符aa匹配，无需继续比较，直接比较模式串的第三个字符b和文本串当前所停留的字符b是否相同
6. 重复直到比较完毕

知道匹配原理后，可以生成next数组。因为next数组实际上模式串是自己和自己匹配的过程

void forNext(int* next,string needle){
    //生成next数组,模式串自己和自己匹配的过程
    int i=1,j=0;
    next[j]=0;  //第一个字符自然没有最长相同前后缀
    for(;i<needle.size();i++){
        //当模式串的前半部分和后半部分不匹配时，回退
        //后半部分相当于文本串，前半部分相当于模式串
        //next数组存的是最长相同前后缀的长度，刚好就是下标+1
        //j回退到最长相同前后缀的下标+1处(即长度),继续匹配，重复回退
        while(needle[i]!=needle[j] && j>0){
            j = next[j-1];
        }
        if(needle[i] == needle[j]){
            //匹配成功，此时j++,i会在循环中自增,j++后刚好就是最长前后缀的长度
            j++;
        }
        next[i] = j;  //next[i]赋值
        }
}

进行匹配

匹配的思路在上方已经说明。

for(;i<haystack.size();i++){
    //当模式串当前字符和文本串当前字符不匹配时，回退
    //模式串当前字符之前和文本串当前字符之前是匹配的
    //next数组存的是最长相同前后缀的长度，刚好就是下标+1
    //模式串指针j回退到最长相同前后缀的下标+1处(即长度),继续匹配，重复回退
    while(j>0 && needle[j]!=haystack[i]){
        j = next[j-1];
    }
    if(haystack[i]==needle[j]){
        //匹配了,模式串指针向前移动,i会在循环中自增
        j++;
    }
    //如果不匹配，j此时为0,i也会自增，从文本串的下一个字符开始匹配
    //匹配完毕，返回下标
    if(j>=needle.size()) return i-needle.size()+1;
}

文本串只需遍历一遍，模式串不匹配时回退到最大匹配部分之后继续匹配

整体代码

class Solution {
public:
    void forNext(int* next,string needle){
        //生成next数组,模式串自己和自己匹配的过程
        int i=1,j=0;
        next[j]=0;  //第一个字符自然没有最长相同前后缀
        for(;i<needle.size();i++){
            //当模式串的前半部分和后半部分不匹配时，回退
            //后半部分相当于文本串，前半部分相当于模式串
            //next数组存的是最长相同前后缀的长度，刚好就是下标+1
            //j回退到最长相同前后缀的下标+1处(即长度),继续匹配，重复回退
            while(needle[i]!=needle[j] && j>0){
                j = next[j-1];
            }
            if(needle[i] == needle[j]){
                //匹配成功，此时j++,i会在循环中自增,j++后刚好就是最长前后缀的长度
                j++;
            }
            next[i] = j;  //next[i]赋值
        }
    }

    int strStr(string haystack, string needle) {
        if(needle.size()==0) return -1;

        //生成next数组
        int next[needle.size()];
        forNext(next,needle);

        //KMP算法匹配字符串
        int i=0,j=0;
        for(;i<haystack.size();i++){
            //当模式串当前字符和文本串当前字符不匹配时，回退
            //模式串当前字符之前和文本串当前字符之前是匹配的
            //next数组存的是最长相同前后缀的长度，刚好就是下标+1
            //模式串指针j回退到最长相同前后缀的下标+1处(即长度),继续匹配，重复回退
            while(j>0 && needle[j]!=haystack[i]){
                j = next[j-1];
            }
            if(haystack[i]==needle[j]){
                //匹配了,模式串指针向前移动,i会在循环中自增
                //如果不匹配，j此时为0,i也会自增，从文本串的下一个字符开始匹配
                j++;
            }
            //匹配完毕，返回下标
            if(j>=needle.size()) return i-needle.size()+1;
        }
        return -1;
    }
};