Template. KMP

KMP字串比對，回傳第一組子字串的位置。
若失敗則回傳-1。

int kmp(const string &T, const string &P) {
    if (P.empty()) return 0;
    
    vector<int> fail(P.size(), 0);
    for (unsigned i = 1, k = 0; i < P.size(); i++) {
        while (k && P[k] != P[i])
            k = fail[k - 1];
        if (P[k] == P[i])
            k++;
        fail[i] = k;
    }

    for (unsigned i = 0, k = 0; i < T.size(); i++) {
        while (k && P[k] != T[i])
            k = fail[k - 1];
        if (P[k] == T[i])
            k++;
        if (k == P.size())
            return i - k + 1; // success
    }
    return -1; // fail
}