Comparing Arrays Homework: Subsequence Function

[chiurox]

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++;
count << "K2: " << k2 << "N2: " << n2 << endl;
}
}
return k2-n2+1;
}


My code works for the first example, but not the second one.

 

[n00bhaus3r]

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.

 

[Nok1]

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.