//
int KMP(int s[MM],int p[MM],int st,int tn,int F[MM])
{
    int i=0,j=0;
    while(i<st&&j<tn)
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=F[j];
        }
    }
    if(j==tn)
        return i-j;
    else
        return -1;
}
void Get(int p[MM],int tn,int F[MM])
{
    F[0]=-1;
    int j=0,k=-1;
    while(j<tn)
    {
        if(k==-1||p[j]==s[k])
        {
            F[++j]=++k;
        }
        else
            k=F[k];
    }
}


const int MM=1e6+5;
int st,tn;
int F[MM];
int t;
int sum;
vector<int>mathp;
void Get(const char s[],int ls,int F[])
{
    F[0]=-1;
    int j=0,k=-1;
    while(j<ls)
    {
        if(k==-1||s[j]==s[k])
        {
            F[++j]=++k;
        }
        else
            k=F[k];
    }
}
int KMP(const char s[],const char p[])//p主
{
    int ls,lt,i=0,j=0;
    ls=strlen(p);
    lt=strlen(s);
    Get(s,lt,F);
    mathp.clear();//tot=0;
    while(i<ls&&(ls-i)>=(lt-j))
    {
        while(j!=-1&&p[i]!=s[j])
            j=F[j];
        i++;
        j++;
        if(j>=lt)
        {
            mathp.push_back(i-j+1);//++tot
            j=F[j];
        }
    }
    return mathp.size();
}