class Solution {
public:
//得到前缀表
    void getNext(int *next,string needle){
        int j=0;
        for(int i=1;i<needle.size();i++){
            while(j>0 && needle[j]!=needle[i]) j=next[j-1];//**j>0**=>j==0是出口
            if(needle[i]==needle[j]) j++;
            next[i]==j;//若写入if中，则该行意思变为当匹配时才给next赋值，没能顾及到回退时的赋值
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        vector<int> next(needle.size());
        getNext(&next[0],needle);
        int j=0;
        for(int i=0;i<haystack.size();i++){
               while(j>0 && haystack[i]!=needle[j]) j=next[j-1];//运用前缀表
            if(haystack[i]==needle[j]) j++;
            if(j==needle.size()) return i-needle.size()+1;
        }
        return -1;
    }
};

find解答

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

暴力

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 时间复杂度O(MN)，空间复杂度O(1)
        int n1 = haystack.size(), n2 = needle.size(), j;
        for (int i = 0; i < n1 - n2 + 1; ++i) {
            if (haystack[i] != needle[0]) continue;
            for (j = 1; j < n2; ++j) {
                if (needle[j] != haystack[i + j]) break;
            }
            if (j == n2) return i;
        }
        return -1;
    }
};