1

I wanted to write a program that compares vector a with vector b. And if vector a is a sub vector of vector b then return true else false. For example:

vector a is 1,2,3

and vector b is 2,3,4,1,1,2,3,56.
So it should be in a contiguous block. And I wrote this nasty code but I want to write this in short way. I don't want to declare any global variables for this problem.

bool i_vec(vector<int>& a, vector<int>  b)
    {
        vector<int> index ( b.size(),0 );
        int counter = 0;

       // if ( a.size() <= b.size() ) {

            for ( int i = 0; i < a.size(); i++ ) {
                for ( int j = 0; j < b.size(); j++ ) {
                    if ( a[i]== b[j]) {
                        index[j] = 1;
                    }
                }
            }

            for ( int i = 0; i < index.size(); i++ ) {
                if ( index[i] == 1 ) {
                    for ( int j = i; j < index.size(); j++ ) {
                        if ( index[j] == 1 ) {
                            counter++;
                        }
                    }
                    if(counter == a.size()){
                        //cout<<"true"<<endl;

                        return true;
                        break;
                    }
                    else{
                        counter = 0;
                        cout<<"false"<<endl;
                        return false;
                      //  continue;
                    }

                }
            }
       // }
         return 0;
    }
5
  • 6
    return std::search(b.begin(), b.end(), a.begin(), a.end()) != b.end(); Short way, and no global variables. Oct 14, 2014 at 4:35
  • @IgorTandetnik Should that line be sufficient? Oct 14, 2014 at 4:56
  • 1
    If you want to look into efficient implementations of this you can read up on: en.wikipedia.org/wiki/…
    – Laserallan
    Oct 14, 2014 at 5:07
  • this is essentially a string search algorithm. if you want an efficient implementation, look into Boyer-Moore
    – sp2danny
    Oct 14, 2014 at 7:03
  • Should that line be sufficient? Have you tried it, and found it lacking? Oct 14, 2014 at 14:00

1 Answer 1

0

Why not using stl algorithm.It's efficient and also makes things sample.

bool i_vec(const vector<int>& a, const vector<int>& b)
{
    for(vector<int>::size_type i = 0; i <= b.size() - a.size(); i++)
    {
        if(equal(a.begin(), a.end(), &b[i]))
        {
            return true;
        }
    }
    return false;
}
7
  • Why not use std::search instead of this entire for loop and std::equal solution? Oct 14, 2014 at 6:39
  • @Blastfurnace So is that a iterative solution? Oct 14, 2014 at 7:11
  • @user4032883: Yes it is. This documentation shows its complexity and an example implementation. Oct 14, 2014 at 7:38
  • @Blastfurnace So which one is more efficient? Oct 14, 2014 at 7:44
  • @Blastfurnace Also I have one more question that has not been answered yet. Could you help me with that. Oct 14, 2014 at 7:45

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.