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

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int m = haystack.size();
        int n = needle.size();
        if (n > m)
        {
            return -1;
        }
        // 构造next数组
        vector<int> next(n + 1, 0);
        for (int cptime = 2; cptime <= n; cptime++)
        {
            string nextstr = needle.substr(0, cptime);
            bool jump=false;
            for (int ncptime = cptime - 1; ncptime >= 1; ncptime--)
            {
                if(jump==true)
                {
                    break;
                }
                for (int i = 1; i <= ncptime; i++)
                {
                    if (nextstr[i - 1] == nextstr[nextstr.size() - ncptime + i - 1])
                    {
                        if (i == ncptime)
                        {
                            next[cptime] = ncptime;
                            jump=true;
                            break;
                        }
                        else
                        {
                            continue;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        // 匹配字符串
        bool flag = false;
        int i = 1, j = 1;
        while (i <= m - n + 1 && j <= n)
        {
            if (needle[j - 1] == haystack[i + j - 1 - 1])
            {
                if (j == n)
                {
                    flag = true;
                    break;
                }
                j++;
                continue;
            }
            else
            {
                if (j - 1 == 0)
                {
                    i++;
                }
                else
                {
                    i = i + j - next[j - 1] - 1;
                }
                j = 1;
                continue;
            }
        }

        return flag == true ? i - 1 : -1;
    }
};

int main()
{
    Solution solution;
    solution.strStr("aabaaabaaac", "aabaaac");
    return 0;
}