2023-07-25力扣今日二题-KMP-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-07-25力扣今日二题-KMP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：

28. 找出字符串中第一个匹配项的下标

题意：

求字符串s1中s2的最小下标

解：

字符串匹配板子题，来复习一下KMP，好久没写了，花了挺久才理清楚

基本思想这里不复习，主要复习写法

next[i]表示当匹配第i个字符时匹配不上，需要退回到的位置，同时next[i]存储的是不包含i的相同前后缀子串的最大长度

构建next数组：m1表示当前匹配的位置，m2表示已经匹配成功的数量，m1初始值1，m2初始值0，初始状态：next[0]=next[1]=0，同时s[m2]刚好指向下一个拿去匹配的字符

当发生不匹配且还存在已经匹配的字符时(m2>0 && needle[m1]!=needle[m2])，m2=next[m2]即回退m2到最后一个能进行匹配的位置，如果此时能匹配，则m2++，然后将结果存在next[m1+1]中

实际使用next数组进行匹配，m1指向主串当前匹配的位置，m2表示模式串内已经匹配成功的数量，这时m1初始值0，m2初始值0，匹配失败时就一直回退到可以匹配的m2或者m2==0，这时候m2就没有再回退的地方了，表示以m1为起点不可行，m1++，匹配成功则m1++;m2++，m2等于模式串长度时计算下标答案

实际代码：

#include<bits/stdc++.h>
using namespace std;
void get_next(const string &needle,vector<int> &next)
{
    int m1=1,m2=0;//m1表示主串位置,m2表示已经匹配的字符数量 
    while(m1<needle.size())
    {
        while(m2>0 && needle[m1]!=needle[m2]) m2=next[m2];
        if(needle[m1]==needle[m2]) m2++;
        next[++m1]=m2;
    }
    //for(auto n:next) cout<<n<<ends;
    //cout<<endl;
}
int strStr(const string haystack,const string needle)
{
    int lg1=haystack.length(),lg2=needle.length();
    if(lg1<lg2) return -1;
    vector<int>next(lg2+1);//next存储匹配i失败时跳转至next[i-1] 
    get_next(needle,next);
    int m1=0,m2=0;//m1表示主串位置,m2表示已经匹配的字符数量 
    while(m1<lg1 && m2<lg2)
    {
        //cout<<m1<<" "<<m2<<endl;
        if(haystack[m1]==needle[m2])//匹配下一个
        {
            //cout<<m1<<"=="<<m2<<endl;
            m1++;m2++;
            if(m2==lg2) return m1-m2;
        }
        else//匹配失败 
        {
            if(m2==0) m1++;
            m2=next[m2];
        }
    }
    return -1;
}
int main()
{
    string s1,s2;cin>>s1>>s2;
    int ans=strStr(s1,s2);
    cout<<ans<<endl;
    return 0; 
}

限制：文章来源地址https://www.toymoban.com/news/detail-605574.html