KMP算法

题目描述
给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1
若出现了多次，则按照升序输出所有出现位置

[要求]
时间复杂度为O(n)O(n)

输入描述:
第一行一个字符串str
第二行一个字符串match

输出描述:
输出若干个数，分别为match在str中出现的位置，从0开始标号。
若不存在输出-1

代码：

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

//获取next数组
vector<int> GetNext(string& match)
{
    vector<int> next(match.size() + 1,0);

    //设为-1是为了标记匹配到头了，如果为0可能会导致死循环
    next[0] = -1;

    //从第二个开始
    int i = 2;

    //用来找公共前后缀的指针
    int k = 0;
    while(i < match.size())
    {
        //如果出现相等，代表出现一个相同的前缀
        if(match[i - 1] == match[k])
        {
            //保存
            next[i] = k + 1;

            //更新k的下标
            k = next[i];
            i++;
        }
        //等于-1代表匹配到头，需要重新开始匹配
        else if(k == -1)
        {
            next[i] = 0;
            i++;
        }
        //否则不为-1代表之前还有匹配，继续往前找
        else 
        {
            k = next[k];
        }
    }
    return next;
}

int main()
{
    string str;
    string match;
    while(getline(cin,str))
    {
        getline(cin,match);

        //获取next数组
        vector<int> next = GetNext(match);

        //用来标记是否出现过匹配的情况，题意需要输出-1
        int flag = 1;

        //双指针
        int i = 0;
        int j = 0;

        //开始循环
        while(i < str.size())
        {
            //如果两个位置的字符相等直接++，判断是否匹配完成即可
            if(str[i] == match[j])
            {
                i++;
                j++;
                if(j == match.size())
                {
                    flag = 0;
                    cout<<i - match.size()<<" ";
                    j = next[j];
                }
            }
            //代表两个位子的字符不想等，kmp就是为了不回溯i而回朔j的
            else
            {
                //j回溯到有相同前后缀的位子
                j = next[j];
                if(j == -1)
                {
                    j = 0;
                    i++;
                }
            }
        }
        if(flag)
            cout<<-1<<endl;
    }
    return 0;
}