Find sequence of elements in vector (C++)

[RileyTheFox]

Hey. So I have 2 vectors of different sizes, and in the bigger one I need to be able to find a sequence of elements that matches the smaller one.

 

Here's an example of the vectors:

 

std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};

How would I find smallVec within bigVec?
bigVec contains the sequence 4, 5, 6.
smallVec also has that sequence.
So how would I find that sequence in bigVec?

 

Help is appreciated, thanks!

[minibois]

Loop through bigVec, until you find the first value of smallVec. Once you find that first number, continue looping through bigVec to find the second number of smallVec. If the subsequent number matches the second number of smallVec, continue doing this again. If not, forget this number and continue doing the same thing.

 

Kinda like this:

for(i = 0; i < bigVec.Count; i++)
{
	for(y = 0; y < smallVec.Count; y++)
    {
		if(bigVec[i] == smallVec[y])
        {
        	// it matches
            if(y == (smallVec.Count - 1))
            {
            	// We got all matches. Not sure what you want to do, but you can simply do i = smallVec.Count and find the location of the match
                // Maybe break, or set somethinbg to true/false?
            }
        }
        else
        {
        	// no match
            break;
        }
    }
    
    if(i == (bigVec.Count -1))
    {
    	// If the bool or whatever is false, or if you have not breaked.. Depends on what you want to do..
        // Number sequence not found
    }
}

 

This is in C#, or C#-like code. I trust you can take this concept and apply it to C++ and make it work for you.

[Sauron]

If you need the sequence to be in that exact order then you need to first find the fist element, then check if the element after that is correct and do the same for the third element. If they are, congratulations, you found it - if they aren't, look for the next occurrence of the first element and repeat.

 

Here's a function that returns the index of bigVector where smallVector first appears in the correct order, or -1 if smallVec doesn't appear at all.

int find(vector<int>& bigVec, vector<int>& smallVec){
  for(int i = 0; i < bigVec.Count - smallVec.Count; i++){	//only check for smallVec where there is enough space for it
    int n;
    for(n = 0; n < smallVec.Count; n++){
      if(bigVec[i + n] != smallVec[n]){		//if one of the elements is incorrect exit the loop and set n to -1
        n = -1;
        break;
      }
    }
    if(n != -1) return i;	//if n isn't -1 it means smallVec was found at index i
  }
  return -1;	//if the function gets here it means smallVec was not found
}

 

[RileyTheFox]

25 minutes ago, minibois said:

Loop through bigVec, until you find the first value of smallVec. Once you find that first number, continue looping through bigVec to find the second number of smallVec. If the subsequent number matches the second number of smallVec, continue doing this again. If not, forget this number and continue doing the same thing.

 

Kinda like this:

for(i = 0; i < bigVec.Count; i++)
{
	for(y = 0; y < smallVec.Count; y++)
    {
		if(bigVec[i] == smallVec[y])
        {
        	// it matches
            if(y == (smallVec.Count - 1))
            {
            	// We got all matches. Not sure what you want to do, but you can simply do i = smallVec.Count and find the location of the match
                // Maybe break, or set somethinbg to true/false?
            }
        }
        else
        {
        	// no match
            break;
        }
    }
    
    if(i == (bigVec.Count -1))
    {
    	// If the bool or whatever is false, or if you have not breaked.. Depends on what you want to do..
        // Number sequence not found
    }
}

 

This is in C#, or C#-like code. I trust you can take this concept and apply it to C++ and make it work for you.

It can find the individual numbers but it fails to find the sequence as a whole thing.

[minibois]

1 minute ago, EVILCAT6 said:

It can find the individual numbers but it fails to find the sequence as a whole thing.

that's what the second for loop is for. But now I realize you need another sort of function to keep looping through the bigVec once you are started on a matching number

[RileyTheFox]

25 minutes ago, minibois said:

- snip -

29 minutes ago, Sauron said:

- snip -

A friend provided a solution that worked perfectly. Here's the code:

for (int i = 0; i <= v1.Length - v2.Length; i++) {
    bool match = true;
    for (int j = 0; j < v2.Length; j++) {
        if (v1[i + j] != v2[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        return true;
    }
}
return false;

 

[Sauron]

3 minutes ago, EVILCAT6 said:

A friend provided a solution that worked perfectly. Here's the code:

for (int i = 0; i <= v1.Length - v2.Length; i++) {
    bool match = true;
    for (int j = 0; j < v2.Length; j++) {
        if (v1[i + j] != v2[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        return true;
    }
}
return false;

 

Seems exactly like mine, it just returns a boolean rather than the position where the sequence is found.

[Unimportant]

On 2/6/2020 at 4:25 PM, EVILCAT6 said:

Hey. So I have 2 vectors of different sizes, and in the bigger one I need to be able to find a sequence of elements that matches the smaller one.

 

Here's an example of the vectors:

 

std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};

How would I find smallVec within bigVec?
bigVec contains the sequence 4, 5, 6.
smallVec also has that sequence.
So how would I find that sequence in bigVec?

 

Help is appreciated, thanks!

Try using the STL as much as possible, it's there for that, results in short and cleaner code and tends to perform better then hand-rolled alternatives.

std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};
	
auto it = std::search(bigVec.begin(), bigVec.end(), smallVec.begin(), smallVec.end());
/* it = iterator to the first occurence of the sequence in bigVec. end if not found.
   if you need the location rather then a iterator use std::distance */
if (it == bigVec.end())
{
	std::cout << "not found\n";
}
else
{
	std::cout << "Sequence starts at element number: " << std::distance(bigVec.begin(), it) << '\n';
}