KMP Algorithm

vector<int> buildLPS(const string &p) {
    int m = p.size();
    vector<int> lps(m);
    for (int i = 1, len = 0; i < m;) {
        if (p[i] == p[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}
vector<int> kmp(const string &s, const string &p) {
    auto lps = buildLPS(p);
    vector<int> matches;
    for (int i = 0, j = 0; i < (int)s.size();) {
        if (s[i] == p[j]) i++, j++;
        if (j == p.size()) { matches.push_back(i - j); j = lps[j - 1]; }
        else if (i < (int)s.size() && s[i] != p[j]) {
            if (j) j = lps[j - 1];
            else i++;
        }
    }
    return matches;
}