Comparing Arrays Homework: Subsequence Function

  • Thread starter chiurox
  • Start date
  • Tags
    Arrays
In summary: Now let's take a look at our two examples. In the first example, subsequence returns 1 when a1 and a2 have the exact same contents, but returns -1 when a1 has some content in it that a2 does not. This is because the inner for loop will keep going until it finds the first occurrence of a2 in a1, which in this case is 3 because there are 5 elements in a2 but only 3 in a1. In the second example, subsequence returns -1 because there are two elements in a2 that appear in a1, but the inner for loop will not keep going because it hits the end of a1.In summary, the function you are looking for takes
  • #1
chiurox
35
0

Homework Statement


OK, so in this CS project, we need to make functions for arrays.
I need to implement a function that does the following:
int subsequence(const string a1[], int n1, const string a2[], int n2);
If all n2 elements of a2 appear in a1, consecutively and in the same order, then return the position in a1 where that subsequence begins. If the subsequence appears more than once in a1, return the smallest such beginning position. Return −1 if a1 does not contain a2 as a continguous subsequence. For example,

string big[10] = { "a", "b", "c", "d", "e" };
string little1[10] = { "b", "c", "d" };
int k = subsequence(big, 5, little1, 3); // returns 1
string little2[10] = { "c", "e" };
int m = subsequence(big, 5, little2, 2); // returns -1

The Attempt at a Solution


So far what I have is this:
int subsequence(const string a1[], int n1, const string a2[], int n2)
{
if (n1 < 0 || n2 < 0) return -1;
int k2 = 0;
//traverse a1, marking off items of a2
for (int k1 = 0; k1 < n1 && k2 < n2; k1++)
{
if (a1[k1] == a2[k2])
{
k2++;
cout << "K2: " << k2 << "N2: " << n2 << endl;
}
}
return k2-n2+1;
}


My code works for the first example, but not the second one.
 
Physics news on Phys.org
  • #2
I am not quite sure what you're asking, but it seems like it's analogous to taking the substring of a String and then using indexOf() to find the first index of that String (applied to Arrays in this case).

Perhaps if you defined what "all n2 elements of a2" mean, we'd be able to help you.
 
  • #3
Your code is WAY more complicated than it has to be :)

First of all, let's look at the problem and try to write out a general solution in pseudocode about what we need to do.

So you start off by checking if either n1 or n2 have length of less than zero, and if so then return -1. This is almost correct, but what would occur if length of one of these was 0? So you should probably make it a <= 0 check.

The algorithm should be as follows

If any of the following conditions are true, then return -1 {
Condition 1: n1 <= 0
Condition 2: n2 <= 0
Condition 3: n2 > n1. // if the length of n2 is bigger than n1, then a2 has more elements than a1​
}
for every element of a1 {
if a1[current element] == a1[first element] then we have a match {
for every element of a2 starting at the second element {
if a2[current element] != a1[current element + offset of a2 array] then {
return -1 because next elements don't match }​
}
next element of a2
return 1 because we ran into a pair, and we didn't break in the inner for loop meaning that we are contained.​
next element of a1​
return -1 since we didnt find anythingOf course, in the algorithm above we assume that given some array a_i has at least n_i elements - otherwise we'd have to add a few more checks at the start of our algorithm.
 
Last edited:

1. What is a subsequence function in relation to comparing arrays?

A subsequence function is a mathematical concept used to compare two arrays and determine if one array is a subsequence of the other. This means that all elements in the first array appear in the same order in the second array, but may not necessarily be adjacent to each other.

2. How does the subsequence function work?

The subsequence function works by iterating through both arrays and comparing each element. If the elements match, the function moves on to the next element in both arrays. If the elements do not match, the function moves on to the next element in the second array. If all elements in the first array are found in the second array in the same order, then the function returns true.

3. What is the time complexity of the subsequence function?

The time complexity of the subsequence function is O(n), where n is the length of the second array. This is because the function only needs to iterate through the second array once to compare all elements with the first array.

4. What happens if the first array is longer than the second array?

If the first array is longer than the second array, the subsequence function will still work and return true if all elements in the second array are found in the first array in the same order. However, if the first array is shorter than the second array, the function will return false.

5. Can the subsequence function be used to compare arrays with non-numerical elements?

Yes, the subsequence function can be used to compare arrays with non-numerical elements. As long as the elements in both arrays are of the same data type, the function will work. It is important to note that the function will compare elements based on their value, not their data type. So, for example, a string "2" will be considered equal to an integer 2.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
820
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
896
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
6K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
  • Engineering and Comp Sci Homework Help
2
Replies
43
Views
4K
Back
Top