KMP算法模板

KMP算法的原理以及图解见如何更好地理解和掌握 KMP 算法?

下面给出KMP算法的模板：

// KMP算法
// 匹配成功返回匹配的起始位置，失败返回-1
// haystack为主串，needle为模式串
int KMP(string haystack, string needle) 
    {
        int len1 = haystack.size(), len2 = needle.size();
        int i = 0, j = -1;
        vector<int> next(len2 + 1);
        next[0] = -1;
        while(i < len2)
        {
            if(j == -1 || needle[i] == needle[j])
            {
                ++i;
                ++j;
                next[i] = j;
            }
            else    
                j = next[j];  
                
        }
        i = 0;
        j = 0;
        while(i < len1 && j < len2)
        {
            if(j == -1 || haystack[i] == needle[j])
            {
                ++i;
                ++j;
            }
            else
                j = next[j];
        }
        if(j == len2)
            return i - j;
        else
            return -1;
    }