Implement StrStr

• Time : $O(A + B)$
• Space : $O(B)$

vector<int> PI(string p) {
    vector<int> pi(p.length());
    for(int i = 1, j = 0; i < p.length(); i++) {
        while(j and p[i] != p[j]) j = pi[j-1];
        if(p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}

int kmp(string s, string p) {
    vector<int> pi = PI(p);
    for(int i = 0, j = 0; i < s.length(); i++) {
        while(j and s[i] != p[j]) j = pi[j-1];
        if(s[i] == p[j]) {
            if(++j == p.length()) return i - p.length() + 1;
        }
    }
    return -1;
}

int Solution::strStr(const string A, const string B) {
    return kmp(A,B);
}