-1
$\begingroup$

I am asked to check if a vector contains another vector as a subvector. For example:

$$v_1 = (4, \underline{3, 4}, 9, 10, 28, 5, 12, \underline{3, 4})$$ $$v_2 = (3, 4)$$

The answer here will be two, since there are two instances of $v_2$ in $v_1$.

I know I have to use "if" but I dont really know how to write it down (I have tried).

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Do you know about for loops? $\endgroup$
    – Subhayan
    Nov 14, 2013 at 14:31
  • $\begingroup$ hint: Try to think of a linear search, that does not stop until it has see the entire vector 1 have a counter for everytime the linear search says 'found it' $\endgroup$
    – Subhayan
    Nov 14, 2013 at 14:47
  • $\begingroup$ Could the down voters explain their down vote? This question is an algorithmic question which is not so trivial (see my comment below). $\endgroup$
    – J.-E. Pin
    Nov 20, 2013 at 16:43

2 Answers 2

Reset to default
1
$\begingroup$

This problem is known as String Matching. In case you don't care about performance Patricks answer is good. Notice that this linear search takes $O(n\cdot m)$ time, vor $n$ being the number of elements in $v_1$ and $m$ being the number of elements in $v_2$. This can be improved by more involved methods, i.e. the Knuth-Morris-Pratt algorithm needs only $O(n+m)$ time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @a-schulz I see two differences with the traditional string matching algorithms. First, here you need to count the number of occurrences of $v_2$ in $v_1$. But, more importantly, since $v_1$ is a vector of integers, the alphabet is potentially unbounded. These two parameters may affect the complexity of the algorithm. $\endgroup$
    – J.-E. Pin
    Nov 20, 2013 at 16:41
0
$\begingroup$

Pseudocode:

Count(source[1...n], target[1...m])
 1. count = 0
 2. for i = 1 to n - m + 1 do
 3.     match = true
 4.     for j = 1 to m do
 5.         if source[i + j - 1] != target[j] then match = false
 6.    if match then count++
 7. print "The count is " + count

The idea is straightforward: check all $n - m + 1$ subvectors of length $m$ and see if they match the target vector. This method will include overlapping occurrences of the target; another method can be used to avoid counting overlapping occurrences. The idea in that case is to step through the source, keeping track of how much of the target you've seen, resetting if you see the wrong thing, and incrementing the count if you see the whole thing.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.