CODEWITHSUNDEEP
c++
MrArO
MrArO

Reputation: 47

Finding if 1 vector is included in 2nd vector

I need to write a program that finds out if one of the 2 vector is included in another one. The program works like this.

1 - Gets the m and n values from input.txt (1st row)

2 - Resizes verctorM and vectorN to m and n, then fills them with numbers from input.txt (2nd row for vectorM, 3rd row for vectorN)

3 - After filling, the program should find out wich one of the vectors has the fewest "characters" by comparing n and m

4 - The program gets the first "character" of "small" vector and start to compare it with the "characters" of "big" vector ()

5 - When the statemant vectorN[i] = vectorM[0] is correct, the program compares the next "characters" if every "character" of "small" vector is in the "big" vector, program output 1, if not continues to compare with 1st "caracter" of "smal" vector, if "small" vector is not included in "big" vector, program outputs 0

Edit - the numbers must be in same order as written in input.txt

Here is the code that I ended up with

#include <iostream> 
#include <vector>
#include <fstream>
using namespace std;

int main() {

int m;
int n;

bool y = false;

vector<int> vectorM;
vector<int> vectorN;

ifstream file1;
file1.open("input.txt");
file1 >> m;
file1 >> n;

vectorM.resize(m);
vectorN.resize(n);

for (int i = 0; i < m; i++){
    file1 >> vectorM[i];
}

for (int i = 0; i < n; i++){
    file1 >> vectorN[i];
}

//this is the part that I need help with


ofstream file2;
file2.open("output.txt");

if (y == false)
    file2 << 0;
else
    file2 << 1;

}

What's the efficent way to compare the "characters" ??

Example, if in input.txt

 4 3
 1 2 3 2
 1 2 3

Program outputs 1, because 1 2 3 is in 1 2 3 2, but if

 2 3
 1 2
 2 3 1

Program outputs 0

Upvotes: 2

Views: 94

Answers (1)

Blastfurnace
Blastfurnace

Reputation: 18652

I think you're asking if a contiguous subsequence can be found inside another range of values. The standard library std::search algorithm does just that.

#include <algorithm>
#include <iostream>
#include <vector>

bool included(const std::vector<int>& seq, const std::vector<int>& sub)
{
    return std::search(seq.begin(), seq.end(), sub.begin(), sub.end()) != seq.end();
}

int main()
{
    auto v1 = std::vector<int>{ 1,2,3,2 };
    auto v2 = std::vector<int>{ 1,2,3 };

    std::cout << std::boolalpha << included(v1, v2) << '\n';

    auto v3 = std::vector<int>{ 1,2 };
    auto v4 = std::vector<int>{ 2,3,1 };

    std::cout << included(v3, v4) << '\n';
}

Demo on ideone.com

Note: I stole Jarod42's function name and coincoin's test data.

Upvotes: 4

Related Questions