KMP

inline void GetNext(char* s)
{
    int l=strlen(s),t;
    next[0]=-1;
    for(int i=1; i<l; ++i)
    {
        t=next[i-1];
        while(s[t+1]!=s[i]&&t>=0)
            t=next[t];
        if(s[t+1]==s[i])
            next[i]=t+1;
        else
            next[i]=-1;
    }
}
inline void KMP(char* s1,char* s2)
{
    ans.clear();
    GetNext(s2);////预处理next数组
    int len_1=strlen(s1);
    int len_2=strlen(s2);
    int i=0,j=0;
    while(j<len_1)
    {
        if(s2[i]==s1[j])
        {
            ++i;
            ++j;
            if(i==len_2)
            {
                ans.push_back(j-len_2+1);
                i=next[i-1]+1;
            }
        }
        else
        {
            if(i==0)
                j++;
            else
                i=next[i-1]+1;
        }
    }
}