力扣 28找到字符串中第一个匹配项的下标 KMP算法

思路：

朴素匹配有很多步骤是多余的

KMP算法能够避免重复匹配

KMP算法主要是根据子串生成的next数组作为回退的依据，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

这里讲一下为什么用模式串的最大公共前后缀求解NEXT数组，参考B站木子喵NEKO的视频【【neko算法课】KMP算法【7期】】 https://www.bilibili.com/video/BV1234y1y7pm/?share_source=copy_web&vd_source=5fc45b3a16cefaa9c36d42d5626cd9e6

用例子思考时，我们可以肉眼看到，需要移动的位置是根据B向后移动几个可以最大化的对齐A(在i之前），意味着找到i前面文本子串(A)与模式子串(B)中重合的部分。

既然i前面都是重合（因为i这里发生了不匹配，前面都匹配），直白说就是一样的，那就不用看文本串了，直接看模式串前后是否有重合的部分，也就是看模式串的最大公共前后缀。如果没看懂可以往下看。

---

kmp整体上分两步

1计算前缀表

2根据前缀表移动两个指针进行匹配

1计算前缀表，就是求解文本串指针回退的位置，

ps:文本串用i指针，模式串用j指针，

以下分别用A,B代指文本串与模式串。

A串中i指针前面（第一次循环时AB发生不匹配的位置）前，用A子串与B子串代称。

当A,B遇到不匹配的字符时，j指针回退，回退依据是当前不匹配位置前一位最大前后缀的长度，

为什么呢？通俗的说就是，不匹配了，看前面有哪些已经最大化的匹配上了，不匹配位置前一位的next值，代表了B自身前后一致的最大长度，根据前面讲的，A子串等效B子串，也就代表了AB子串前后一致的最大长度，也就代表了A子串的后面与B子串的前面一致的最大长度，也就是B需要向后移动几个字符，而j指针的移动代表着B向后移动，也就是j指针要移动到的位置。

j回退到上次最大化匹配的位置

如果还不匹配，再次查看不匹配位置前一位next的值。

如果匹配，j加一，也就意味着j向后移动一位，i向后移动写在了for循环里。

同时每次更新next[i]

void getNext(string s,int next[])
{
    int j = 0;
    next[0] = 0;
    for(int i = 1;i<s.size();i++)
    {
        while(j>0 && s[i] != s[j]) j = next[j-1];
        if(s[i] == s[j]) j++;
        next[i] = j;
    }
}

2 模拟匹配过程

如果不匹配，按着next数组回退j指针，如果匹配，J增一

最后如果j指向了模式串的末尾，说明找到了完整匹配，返回匹配的起始下标

int strStr(string s,string t)
{
    if(t.size()==0) return 0;
    get_Nxt(t,next);
    int j = 0;
    for(int i = 0;i<s.size();i++)
    {
    while(j>0 && s[i]!=s[j]) j = next[j-1];
    if(s[i] == t[j]) j++;
    if(j == t.size()) return (i - t.size()+1);
    }
}

原文地址：https://blog.csdn.net/weixin_43261508/article/details/140590736

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！