-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).

$\endgroup$
  • 1
    $\begingroup$ Do you know about for loops? $\endgroup$ – Subhayan Nov 14 '13 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 '13 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 '13 at 16:43
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.

$\endgroup$
  • $\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 '13 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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