KMP 알고리즘 문자열 일치

kmp 알고리즘으로 문자열 일치, kmp 알고리즘 소개

int strStr(string haystack, string needle) {
        if (needle.size() == 0)
            return 0;
        vector<int> next(needle.size(), 0);
        for (int i = 2; i < next.size(); ++i)
        {
            int j = next[i - 1];
            while (j > 0 && needle[j] != needle[i - 1])
                j = next[j];

            if (needle[j] == needle[i-1])
                next[i] = j + 1;

        }

        int k = 0;
        while (k < haystack.size())
        {
            bool flag = true;
            for (int i = 0; i < needle.size(); ++i)
            {
                if (k + i >= haystack.size())
                    return -1;
                if (needle[i] != haystack[k + i])
                {
                    if (i == 0)
                        ++k;
                    else
                        k += i - next[i];

                    flag = false;
                    break;
                }
            }
            if (flag)
                return k;
        }

        return -1;
    }