Numbers In Pi

• Time : O(m * len(n))
• Space : O(k)

#include <vector>
using namespace std;

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

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

int numbersInPi(string pi, vector<string> numbers) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> intervals;

    for(auto& n : numbers) {
        auto pos = kmp(pi, n);
        for(auto& p : pos)
            intervals.push({p, p + n.length()});
    }

    int p = 0, res = -1, n = pi.length(), ma = 0;
    while(!intervals.empty() and p < n) {
        while(!intervals.empty() and p >= intervals.top().first) {
            ma = max(intervals.top().second, ma);
            intervals.pop();
        }
        if(ma > p) {
            p = ma;
            res++;
        } else return -1;
    }
    return p == n ? res : -1;
}