# Determine whether one vector is a prefix of the other

Exercise 5.17:

Given two vectors of ints, write a program to determine whether one vector is a prefix of the other. For vectors of unequal length, compare the number of elements of the smaller vector. For example, given the vectors containing 0, 1, 1, and 2 and 0, 1, 1, 2, 3, 5, 8, respectively your program should return true.

This executes correctly, but I just want to get this double-checked.

#include <iostream>
#include <vector>

using std::vector; using std::cout; using std::endl;

int main()
{
vector<int> v1{ 0, 1, 1, 2, 3, 5, 8 };
vector<int> v2{ 0, 1, 1, 2 };
if (v1.size() < v2.size()){
cout << "Using v1 as the prefix to v2" << endl;
for (int smallIndex = 0, largeIndex = 1; smallIndex != v1.size(); ++smallIndex, ++largeIndex){
if (v1[smallIndex] == v2[largeIndex])
cout << "v1 at position " << smallIndex << " is a prefix for v2 at postion " << largeIndex << endl;
}
}
else if (v1.size() > v2.size()){
cout << "Using v2 as the prefix to v1" << endl;
for (int smallIndex = 0, largeIndex = 1; smallIndex != v2.size(); ++smallIndex, ++largeIndex){
if (v2[smallIndex] == v1[largeIndex])
cout << "v2 at position " << smallIndex << " is a prefix for v1 at position " << largeIndex << endl;
}
}
else {      //  v1.size() == v2.size() only comparing the first as the prefix to the second
cout << "Size of v1 and v2 are the same, using v1 as the prefix to v2" << endl;
for (int smallIndex = 0, largeIndex = 1; largeIndex != v1.size(); ++smallIndex, ++largeIndex){
if (v1[smallIndex] == v2[largeIndex])
cout << "v1 at position " << smallIndex << " is a prefix for v2 at postion " << largeIndex << endl;
}
}
}

• it should check if v2 is the prefix of v1? so v2 is the prefix of v1 because have: 0, 1, 1, 2 right? Aug 15 '14 at 15:35
• A lot of duplicate code there. By using a function you can reduce this. Aug 15 '14 at 18:09
• Thanks for the help guys, it was really early and I was having a hard time understanding the prefix part. I see some good suggestions but the book has only talked about iterators, loops and a few other small basic things. I don't want to stray too far from using googled methods to figure out the problem and stick more closely to using the functions taught up to this chapter in the book. Aug 15 '14 at 22:43

For a prefix search, you can use std::mismatch() in <algorithm>.

bool isPrefix(const std::vector<int>& v1, const std::vector<int>& v2) {
if (v1.size() > v2.size()) {
return v2.end() == std::mismatch(v2.begin(), v2.end(), v1.begin()).first;
}
return v1.end() == std::mismatch(v1.begin(), v1.end(), v2.begin()).first;
}

• I probably should have made the qualification that the OP would still have to prearrange their inputs or pay an extra cost in calculating/comparing distances post-std::mismatch(). Aug 18 '14 at 21:48
• actually, I was thinking of a different function, you can just check if either iterator in the pair is the end. Aug 18 '14 at 22:05
• At least as I read things, when you supply only three iterators, you must ensure that the third iterator points to the beginning of a sequence at least as long as the distance between the first two, or else you get undefined behavior. Aug 18 '14 at 22:22
• That appears to be very true, guess you have to check distances prior to checking for mismatch. Probably just easier to use your method of finding the minimum distance and passing the equivalent subsequences into std::equal(). Aug 18 '14 at 22:35
• Is there any reason why you are using cbegin instead of begin? The vectors are const anyway so the latter will return the same and is shorter. Aug 19 '14 at 11:19

Right now your code has quite a bit of repetition--basically three repetitions, for v1 shorter than v2, v2 shorter than v1, and v1/v2 being the same length.

It seems like it would be easier to find the shorter of the two, then compare from zero to that size:

bool is_prefix(std::vector<int> const &v1, std::vector<int> const &v2) {
size_t len = std::min(v1.size(), v2.size());

for (size_t i=0; i<len; i++)
if (v1[i] != v2[i])
return false;
return true;
}


You can also use std::equal to do most of the work:

    size_t len = std::min(v1.size(), v2.size());

return std::equal(v1.begin(), v1.begin()+len,
v2.begin(), v2.begin()+len);


Of course, you can also make it generic so it can handle different container types and/or different contained types, but I'll leave that discussion for another day.

Other details:

1. Rather than printing out a running commentary for every position in the arrays, I'd rather see (as above) a single result to indicate whether one is a prefix of the other or not.
2. I'd avoid using endl. All you really want here is a new-line, so just print out '\n'.
3. As shown above, it looks to me like the intended logic is rather simpler than what your code uses.

Offhand, this doesn't look 100% correct. For example, if both vectors are empty, it will loop forever on the bottom for loop (I ran it with 2 empty lists and it segfaults). Also, your program prints out a lot, but never actually says if the vector is a prefix of the other vector.

You should make a function like

bool isPrefixOf(vector<int> v1, vector<int> v2){}


and then call that in the main method with your two vectors.

The logic in your code seems off too. You're comparing the wrong values of the vectors (There shouldn't be a smallIndex and a largeIndex since you should be comparing them at the same index.) If you're looking to actually find if it's a prefix, put them like so in the function (this is the last loop)

    for (int smallIndex = 0; smallIndex != v1.size(); ++smallIndex){
if (v1[smallIndex] != v2[smallIndex])
return false;
}
return true;

• If you are not going to change the vectors then you should pass them as const reference rather than by value. Aug 15 '14 at 18:11