自己写的KMP算法，出了点问题

Question

#include<iostream>
#include<string>
using namespace std;

int* get_next(string needle)
{
    int* next = new int[needle.size()];
    int i = 0, j = -1;
    next[0] = -1;
    while (i < needle.size() - 1)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            ++i, ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}

int KMP(string needle, string haystack)
{
    int* next = get_next(needle);
    int i = 0, j = 0;
    while (i < haystack.size() && j < needle.size())
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            ++i, ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == needle.size())
    {
        return i - j;
    }
    return -2;
}

int main()
{
    string haystack = "abcacbcdf";
    string needle = "acb";
    cout << KMP(haystack, needle);
    return 0;
}

该程序最终返回的是-2，但是按照KMP算法应当返回3，我进行调试发现i = 1, j = -1 时就跳出了while，有点搞不明白为什么，向各位请教一下原因

Answer 1

C++中string类size() 函数的返回值是无符号数,所以判断的地方需强制类型转换下,供参考：

#include<iostream>
#include<string>
using namespace std;
int* get_next(string needle)
{
    int* next = new int[needle.size()];
    int i = 0, j = -1;
    next[0] = -1;
    while (i < (int)needle.size() - 1)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            ++i, ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}
int KMP(string needle, string haystack)
{
    int* next = get_next(needle);
    int i = 0, j = 0;
    while (i < (int)haystack.size() && j < (int)needle.size())
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            ++i, ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == (int)needle.size())
    {
        return i - j;
    }
    return -2;
}
int main()
{
    string haystack = "abcacbcdf";
    string needle = "acb";
    cout << KMP(haystack, needle);
    return 0;
}