Program A: Music Pattern
Context
An embedded system runs continuously but has limited memory. The system has a microphone and is "listening" for tones of a specific pitch (notes A, B, etc.) The objective is to detect the shortest subsequence of the pattern: an E followed by any number of (zero or more) arbitrary tones, followed by an F, followed by any number of arbitrary tones, followed by an F. The output at the end of a run is the length of the shortest subsequence in the input.
So, for example, the input
A−E−A−F−A−E⏟l=5−A" role="presentation" >A−E−A−F−A−E⏟l=5−A
producesl=5" role="presentation" >l=5because the shortest (and only) subsequence E ... F ... E is 5 tones long. The sample input
A−B−E−C−E−A−F−A−E−A" role="presentation" >A−B−E−C−E−A−F−A−E−A
produces 5 as well because although the subsequenceE−C−E−A−F−A−E" role="presentation" >E−C−E−A−F−A−E matches, it is longer than the subsequenceE−A−F−A−E" role="presentation" >E−A−F−A−E.
Likewise, in a longer input
C−C−E−C−C−F−C−C−E−C−C−E−C−F−C−E−C−C−E−C−F−C−E−C−C" role="presentation" >C−C−E−C−C−F−C−C−E−C−C−E−C−F−C−E−C−C−E−C−F−C−E−C−C
the sequence appears multiple times but the length of the shortest is still 5. If the sequence ends without a complete E ... F ... E, then the minimum distance is 999,999,999.
Details
Write a C++ program that reads a sequence of tones (one per line on the standard input) and at the end output the length of the shortest E...F...E pattern. In addition to outputting the shortest length, a correct solution must have a space complexity of O(1). In other words, the input could number in the millions of tones and since memory of the embedded system is limited, it cannot store every element. (However, there will not be 100s of millions of input tones, so the "magic" number 999,999,999 above is safe to use to indicate "no patterns found".)
NOTE: The input looks like this (one whitespace delimited string) per line with no hyphens in the input at all.
A E A F A E A
and the output is simply
5
The output ofE−F−E" role="presentation" >E−F−Eis 3 and of the empty input is XXXXXXXXXX.
As with the programming assignments in this course, comments, variables/function names, indentation, etc. will be evaluated. Except for the cases explicitly mentioned here, you do not need to check for errors (like input that is not a note).
What to Submit
Submit a single, complete C++ file. Your submission will be compiled with the commandg++ -g where is the name of the file you submit.