The key insight here is to introduce a difference array, i.e., the different between previous and next entry.

Obviously, if the pattern exists in the wall, then the same range of in the difference pattern match too.

Claim: if we can find the difference array A in the B’s difference array, then in the same range in the orignal arrays, we can find the pattern in the wall by shifting pattern up or down as a whole Proof: when we locate such pattern match in the difference array, we can then add a delta to make the first element match, and then because each of the following diff entry matches, delta + prefixSum[i] match for all entries in the pattern range => this means the actual shift matches

Therefore, we convert both to the diff array, contactiate 2, with a speical char separate the concact, and then run Z-algorithm, and we look for all i where z[i] = length(p) - 1. -1 because for this diff array we start with a[1] - a[0], a[0] is completely free so that we can shift it up or down!!!