算法1

KMP

class Solution {
public:
    int strStr(string s, string p) {
        if(p.empty()) return 0;
        int n = s.size();
        int m = p.size();

        //得到next数组
        int next[m+1];
        int j = 0, k = -1;
        next[j] = k;
        while(j < m){
            if(k == -1 || p[j] == p[k]){
                j++;
                k++; 
                next[j] = k;
            }else{
                k = next[k];
            }
        }

        //kmp算法
        int i = 0;
        j = 0;
        while(i < n && j < m){
            if(j == -1 || s[i] == p[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        //printf("%d %d %d\n", i, j, m);
        if(j == m){
            return i - j; 
        }else{
            return -1;
        }

    }
};