The Number of Subarrays That Match a Pattern II is the harder variant of Pattern I, designed for larger arrays where naive O(n*m) matching would TLE. The same encoding approach applies (differences → ternary signs), but now requires a fully O(n + m) KMP or O(n) rolling hash implementation. This hard coding problem tests efficient string matching algorithm implementation.
ThoughtWorks and Autodesk ask this to test full KMP or Z-algorithm implementation on non-character sequences. It validates that candidates can implement these algorithms for arbitrary comparable sequences, not just characters. The array, string matching, hash function, and rolling hash interview pattern is comprehensively tested at the implementation level.
KMP on ternary sequence. Encode nums differences into a ternary array as in Pattern I. Build the KMP failure function for pattern. Run KMP search on the encoded array to count all pattern occurrences. Total time: O(n + m).
Rolling hash alternative: Assign distinct large primes to -1, 0, 1, compute rolling polynomial hash over windows of pattern length. Compare hashes.
Large nums array, pattern=[1,0,-1]. Encode nums differences. Apply KMP to find all windows matching [1,0,-1]. KMP builds failure table for pattern in O(m). Then scans encoded array in O(n). Each full match increments the count.
KMP failure function computation is a critical skill. Practice implementing it from scratch: fail[0] = 0; for i≥1, if pattern[i] == pattern[fail[i-1]], extend; otherwise backtrack until matching or fail[0]. The KMP search loop uses the failure function for O(1) amortized backtracking. Being able to implement KMP cleanly on generic sequences (not just char arrays) demonstrates advanced string algorithm mastery — a differentiator in hard string interview questions.
