Homework 11: Counting Sub-Sequences
This problem comes from the recent qualification round of Google Code Jam 2009.
Last month, the problem was to find a common sub-sequence between two given sequences.
This month, I will give you a long sequence and a sub-sequence and your job is to count how many times the sub-sequence appears in the longer sequence.
Example 1:
Long = 1 2 3 4 5 1 2 3 4 5
Sub = 1 2
The sub-sequence “1 2” appears 3 times in the long sequence.
Example 2:
Long = 1 1 2 2 3 3
Sub = 1 2 3
The sub-sequence “1 2 3” appears 8 times in the long sequence.
You may do this using the language of your choice. I encourage you to solve it in a language you would like to learn, rather than one you are an expert in, to broaden your horizon.
Try to avoid brute-force solutions where possible. Your program should handle Google’s “Large Input”, which will take ages to run with a brute-force solution.
Bring your solution to our September meeting.
Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).