KMP算法

前置技能：前缀数组
参考博客：KMP算法（kuangbin）

const int maxn=1e5;
int Next[maxn];
/*求前缀数组*/
/*t[0]对应Next[1]*/
/*Next[0]=-1*/
void getNext(string t)
{
    int i=0,j=-1,n=t.length();
    Next[0]=-1;
    while(i<n)
    {
        if(j==-1||t[i]==t[j])
            Next[++i]=++j;
        else j=Next[j];
    }
}
/*求 t 在 s 中出现的次数（可交叉）（即:s="bababa" t="baba" KMP_count()=2）*/
int KMP_count(string s,string t)
{
    int ans=0,slen=s.length(),tlen=t.length();
    if(slen==1&&tlen==1)
    {
        if(s==t) return 1;
        else return 0;
    }
    getNext(t);
    for(int i=0,j=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;
}
/*求 t 在 s 中出现的第一个位置（从0开始数）*/
int KMP_index(string s,string t)
{
    int i=0,j=0,slen=s.length(),tlen=t.length();
    getNext(t);
    while(i<slen&&j<tlen)
    {
        if(j==-1||s[i]==t[j])
            i++,j++;
        else j=Next[j];
    }
    if(j==tlen) return i-tlen;
    else return -1;
}