Problem Statement

Sequence Detector Kabir builds embedded controllers and is currently studying finite-state machines that watch an incoming bit stream for a fixed pattern. Such a circuit is called a sequence detector, and it can be built in one of two flavours: overlapping or non-overlapping. A sequence detector is a digital circuit that flags every occurrence of a target bit pattern inside a longer stream of bits. Depending on how the detector's states are wired, matches may or may not be allowed to share bits with each other. Here is how a non-overlapping detector for pattern 101 behaves on a stream: 101001011010001101 Scanning the stream above (call it Series 1), a non-overlapping detector reports four matches of 101 , because once a match consumes its three bits, scanning resumes strictly after them. Contrast that with an overlapping detector on the same target pattern: 1011001010 On this stream (Series 2), an overlapping detector reports three matches of 101 . The tail 10101 contains two matches t