class Solution {
public:
    int strStr(string haystack, string needle) {
        int i=0 , j=0;
        if (needle[0]=='\0' || haystack == needle) return 0;
        if(haystack.size() < needle.size()) return -1;
        while(i<= haystack.size()-needle.size())
        {
            // cout<<haystack[i]<<endl;
            if(haystack[i]==needle[0])
            {
               string temp = haystack.substr(i,needle.size());
            //    cout<<"temp "<<temp<<endl;
               if(temp == needle) return i;
            }
            i++;
        }
        return -1;
    }
};

#include <iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include <algorithm>
#include<map>
using namespace std;
class Solution {
public:
    void getNext(int* next, const string& s) //计算next数组
    {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++) 
        {
            while (j >= 0 && s[i] != s[j + 1])  //前后缀不同时后退，是while不是if，因为要连续后退不能只后退一次
            {
                j = next[j];
            }
            if (s[i] == s[j + 1]) //前后缀相同时，增加前后缀长度
            {
                j++;
            }
            next[i] = j; //i点时前后缀长度赋值
        }
    }
    int strStr(string haystack, string needle) 
    {
        if (needle.size() == 0) //如果模式组是长度为0，直接返回0
        {
            return 0;
        }
        int *next = new int[needle.size()]; //动态申请next数组，长度和模式串相同
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.size(); i++) //循环文本串
        {
            while (j>=0 && haystack[i] != needle[j+1]) //文本串和模式串不匹配，模式串回退
            {
                j = next[j];
            }
            if (haystack[i] == needle[j + 1]) //文本串和模式串匹配，模式串前进
            {
                j++;
            }
            if (j == needle.size() - 1) //文本串和模式串成功，前后缀公共长度为模式串-1
            {
              delete[] next;
                return (i - needle.size() + 1); //匹配成功字符串的头下标
            }
        }
    delete[] next;
        return -1;
    }
};
int main() {
    Solution a;
    string h = "sadbutsad";
    string n = "sad";
    int b = a.strStr(h, n);
    cout << b;
    return 0;
}

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int left=0 ; left < haystack.size() ;left++)
        {
            if(haystack[left] == needle[0])
            {
                for(int right = left ,i=0; right < haystack.size() && i<needle.size(); right++,i++)
                {
                    if(haystack[right] == needle[i])
                    {
                        if(i==needle.size()-1)
                        {
                            return left;
                        }
                        continue;
                    }
                    else break;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    void getNext(int *next ,const string &s)
    {
        int j=-1;
        next[0] = j;
        for(int i=1 ; i<s.size();i++)
        {
            while( j>=0 && s[i] != s[j+1] )
                j = next[j];
            if(s[i] == s[j+1]) j++;
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
       if(needle.size() == 0 ) return 0;
       int next[needle.size()];
       int j=-1;
       getNext(next , needle);
       for(int i=0 ; i<haystack.size() ;i++)
       {
            while(j>=0 && haystack[i] != needle[j+1])
                j = next[j];
            if(haystack[i] == needle[j+1]) j++;
            if( j == needle.size() - 1 )
                return (i-needle.size()+1);
       }
       return -1;
    }
};