字符串模式匹配KMP

主串S: [0...n-1]
模式串T: [0...m-1]
模式匹配：返回模式串在主串中的位置

蛮力法

int IndexMatch(char s[],char t[])
{
    int n=strlen(s);
    int m=strlen(t);
    for(int i=0;i<=n-m;i++)
    {
        int j=0;
        while(j<m && s[i+j]==t[j])
            j++;
        if(j==m) return i;
    }
    return -1;
}

简单模式匹配算法的最坏时间复杂度为O(nm).

KMP算法

kmp算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。每当一趟匹配过程中出现字符不相等时，不需要回溯 i 指针，而是通过修改 j 指针，将模式串向右尽可能远的滑动一段距离，继续进行比较。具体就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
kmp算法通过一个O(m)的预处理，是匹配的时间复杂度降为O(n+m).

详细推导过程可参考博客：https://www.cnblogs.com/yjiyjige/p/3263858.html

next[j]表示当S[i] != T[j] 时，模式串中需要重新和主串匹配的位置。

#include<iostream>
#include<cstring>
using namespace std;

const int N=100000;
int Next[N];
char s[N],t[N];
int slen,tlen;

//next[j]表示当s[i]!=t[j]时,模式串t中需要重新和主串匹配的位置
void makeNext()
{
    int j,k;
    j=0, k=-1;
    Next[0]=-1;
    while(j<tlen)
    {
        if(k==-1 || t[j]==t[k]) //当k为-1时,需要移动j,同时k要置0
        {
            Next[++j]=++k;
        }else k=Next[k];
    }
}

//返回模式串t在主串s中首次出现的下标
int kmpIdx()
{
    int i=0,j=0;
    while(i<slen && j<tlen)
    {
        if(j==-1 || s[i]==t[j]) //当j为-1时,要移动的是i,当然j也应置0
        {
            i++; j++;
        }else j=Next[j];  //i不需要回溯,j回溯到指定位置
    }
    if(j==tlen)
        return i-tlen;
    else return -1;
}

//返回模式串t在主串s中出现的次数
int kmpCnt()
{
    int ans=0;
    int i,j;
    if(slen==1 && tlen==1)
    {
        if(s[0]==t[0]) return 1;
        else return 0;
    }
    j=0;
    for(i=0;i<slen;i++)
    {
        while(j>0 && s[i]!=t[j])
        {
            j=Next[j];
        }
        if(s[i]==t[j])
            j++;
        if(j==tlen)
        {
            ans++;
            j=Next[j];
        }

    }
    return ans;
}

int main()
{
    cin>>s>>t;
    slen=strlen(s);
    tlen=strlen(t);
    makeNext();
    cout<<"模式串在主串中首次出现的位置:"<<kmpIdx()<<endl;
    cout<<"模式串在主串中出现的次数:"<<kmpCnt()<<endl;
    return 0;
}