leetcode-串

class Solution {
public:

    int* buildNext(string p){
        int j=0, m = p.size(), *next = new int[m];
        int t = next[0] = -1;
        while(j < m-1){
            if(0>t || p[j] == p[t]){
                next[j+1] = t+1;
                j++; t++;
            }else
                t = next[t];
        }
        return next;
    }

    int strStr(string t, string p) {
        
        int n = t.size(), i=0;
        int m = p.size(), j=0;
        
        if(n==0&&m==0) return 0;
        else if(n==0) return -1;
        else if(m==0) return 0;

        int* next = buildNext(p);
        while(i<n && j<m){
            if(0>j || t[i] == p[j]) 
                {i++; j++;}
            else
                j=next[j];

        }
        delete[] next;
        if(j==m) return i-j;
        else return -1;
    }
};