[数据结构与算法]KMP算法（含优化）的c++实现

1.next数组

 vector<int> next(string target)
    {   
        int i=0,j=-1;
        vector<int> nxt(target.length(),0);
        nxt[0]=-1;
        while(i<(target.length()-1))
        {
            if((j==-1)||(target[i]==target[j]))
            {
                i++;
                j++;

                     nxt[i]=j;

               
            }
            else
            {
                j=nxt[j];
            }
        }
        return nxt;
    }

2.next数组?（优化后）

 vector<int> next(string target)
    {   
        int i=0,j=-1;
        vector<int> nxt(target.length(),0);
        nxt[0]=-1;
        while(i<(target.length()-1))
        {
            if((j==-1)||(target[i]==target[j]))
            {
                i++;
                j++;
                if(target[i]==target[j])
                {
                    nxt[i]=nxt[j];
                }
                else{
                     nxt[i]=j;
                }
               
            }
            else
            {
                j=nxt[j];
            }
        }
        return nxt;
    }

3.KMP算法

int strStr(string &source, string &target) {
        if(target.empty())
        {
            return 0;
        }
       vector<int> n=next(target);
 
        while(i<source.length())
        {
            if((j==-1)||(source[i]==target[j]))
            {
                i++;
                j++;
            }
            else{
                j=n[j];
            }
            if(j==target.length())
            {
                return i-j;
                break;
            }

        }
        return -1;
    }

?