kmp.cc

int Kmp(const std::string& a, const std::string& b) {
    if (b.empty()) {
        return 0;
    }
    int n = (int)b.size();
    std::vector<int> p(n);
    if (n > 1) {
        p[1] = 0;
    }
    for (int i = 2, j = 0; i < n; i++) {
        while (b[i-1] != b[j] && j > 0) {
            j = p[j];
        }
        if (b[i-1] == b[j]) {
            p[i] = j + 1;
        } else {
            p[i] = 0;
        }
        j = p[i];
    }
    int i = 0, j = 0;
    for (; i < (int)a.size() && j < n; i++) {
        while (a[i] != b[j] && j > 0) {
            j = p[j];
        }
        if (a[i] == b[j]) {
            j++;
        }
    }
    if (j == n) {
        return i - j;
    } else {
        return -1;
    }
}