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

class Solution
{
public:
    vector<int> GetNext(string m)
    {
        vector<int> next(m.size() + 1, 0);
        for (int i = 2; i <= m.size(); i++)
        {
            int len = next[i - 1];
            while (m[len] != m[i - 1] && len > 0)
            {
                len = next[len];
            }
            if (m[len] == m[i - 1])
            {
                next[i] = len + 1;
            }
        }
        return next;
    }

    int strStr(string haystack, string needle)
    {
        vector<int> next=GetNext(needle);
        int m=haystack.size();
        int n=needle.size();
        int i=1,j=1;
        bool flag=false;
        while(i<=m-n+1&&j<=m)
        {
            if(haystack[j-1]==needle[j-i])
            {
                if(j-i+1==n)
                {
                    flag=true;
                    break;
                }
                else
                {
                    j++;
                    continue;
                }
            }
            else
            {
                if(i!=j)
                {
                    i=j-next[j-i];
                }
                else
                {
                    i++;
                    j++;
                }
                continue;
            }
        }
        return flag==true? i-1:-1;
    }
};