find-pattern-in-infinite-stream-ii.cpp

// Time:  O(p + n)
// Space: O(p)

// kmp
class Solution {
public:
    int findPattern(InfiniteStream* stream, vector<int>& pattern) {
        const auto& getPrefix = [](const auto& pattern) {
            vector<int> prefix(size(pattern), -1);
            int j = -1;
            for (int i = 1; i < size(pattern); ++i) {
                while (j > -1 && pattern[j + 1] != pattern[i]) {
                    j = prefix[j];
                }
                if (pattern[j + 1] == pattern[i]) {
                    ++j;
                }
                prefix[i] = j;
            }
            return prefix;
        };

        vector<int> result;
        const vector<int> prefix = getPrefix(pattern);
        int j = -1;
        for (int i = 0; ; ++i) {
            const auto d = stream->next();
            while (j > -1 && pattern[j + 1] != d) {
                j = prefix[j];
            }
            if (pattern[j + 1] == d) {
                ++j;
            }
            if (j == size(pattern) - 1) {
                return i - j;
            }
        }
        return -1;
    }
};