Finding subset of integers
can anyone write a code for this:
Searching a set of Integers
You are given two sets of integers. S1 and S2. The size of S1 is less than sizeof S2, i.e. the number of integers in S1 is less than the number of integers in S2.
Neither S1, not S2 can be an empty set.
You have to find out whether the sequence of integers of S1 is there in S2.
e.g. S1 = { 1, 5, 6 }, and S2 = { 4, 7, 9, 1, 5, 6 }.
Here, you have found the S1 in S2 subset.
S1 = { 1, 9 }, and S2 = {5, 8, 9 , 1 }
Here, S1 is not found in S2
S1 = { 2, 5 }, and S2 = {6, 2, 5, 7, 2, 5, 1 }
Here, S1 is found in S2, twice. You need to return all the instances.
You can do this in C/C++
[731 byte] By [
calvin03] at [2007-11-11 8:34:08]
# 1 Re: Finding subset of integers
The real question is whether YOU can write this code ... and what help others can give you in your work so that you can accomplish this task.
This is a straight forward pattern matching assignment. Probably one most easily done by brute force since you are dealing with short sequences. If you are curious about how to do this task well, or in a more complex case, search for information on the Boyer-Moore Algorithm or the Knuth-Morris-Pratt Algorithm.
The brute force approach starts with a search for the first occurrence in S2 for the first number in S1. When you find it, ask "do I have a match in S2(x+1) with S1(y+1)?" If so, continue your comparison until you run out of entries in your probe S1 (you have a complete match) or you do not match. Remember to hold your place of the last attempted match in S2 so that you can continue your searching there with whether or not you have a match for the first element of S1.
Oh, I just thought about the case where you have a repeating probe pattern - the element in S2 you need to keep track of as the "start over place" is the one after the first match in this current set of matching.
nspils at 2007-11-11 21:01:11 >
