kmp算法模板

View Code 

void get_next(const string sub, int *next)
{
    int len=sub.length();
    int i,k;
    next[0]=k=-1;
    for (i=0; i<len;)
    {
        if (k==-1 || sub[i]==sub[k])
        {
            k++; i++;
            if (sub[k]!=sub[i]) next[i]=k;
            else next[i]=next[k];    //避免重复计算优化next数组
        }
        else k=next[k];
    }
}

View Code 

int KMP(const string str, const string sub, const int *next)    //返回子串在主串中的起始位置下标        
{
    int i,j;
    int len1=str.length();
    int len2=sub.length();
    for (i=0, j=0; i<len1 && j<len2;)
    {
        if (j==-1 || str[i]==sub[j])
        {