DiffPush Tier Arrays · Hard O(n) · O(n)
A deep packet inspector folds the bytes of each packet into a single integer fingerprint and keeps the packets in arrival order. A security rule triggers on any contiguous run of packets whose combined XOR fingerprint equals a known signature. Count how many such runs exist in the capture.
Input: An integer N, an array A of N non-negative fingerprints, and an integer B, the signature to match.
Output: The number of contiguous subarrays of A whose bitwise XOR equals B.
1 <= N <= 10^50 <= A[i] <= 10^90 <= B <= 10^9Input: {"N":4,"A":[1,2,3,2],"B":2}
Output: 3
The whole capture folds to 2, and so do the two single-packet runs holding 2, giving three matches.
Input: {"N":5,"A":[4,2,2,6,4],"B":6}
Output: 4
Four distinct runs fold to the signature, including overlapping runs that share packets.