#include <cstddef>
#include <iostream>

/***************************************************
 * Finding an array within another array
 *
 * Determine whether all the entries of one array
 * appear consecutively and in the same order within
 * another array.
 *
 * If they do, return the first index at which the
 * smaller array occurs.
 ***************************************************/

// Function declarations
std::size_t first_in_array(
    int         const array1[],
    std::size_t const capacity1,
    int         const array2[],
    std::size_t const capacity2
);

int main();

// Function definitions
int main() {
    int array1[1]{ 18 };
    int array2[1]{ 42 };
    int array3[2]{ 25, 26 };
    int array4[2]{ 25, 27 };

    int array5[8]{
        19, 20, 21, 22, 23, 24, 25, 26
    };

    int array6[8]{
        19, 20, 21, 22, 23, 24, 25, 27
    };

    int array[30]{
        10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
        20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
        30, 31, 32, 33, 34, 35, 36, 37, 38, 39
    };

    // The empty array occurs at index 0.
    std::cout << first_in_array(
        nullptr, 0, array, 30
    ) << " = 0" << std::endl;

    std::cout
        << "Searching for an array of capacity 1; "
        << "not found is 30:"
        << std::endl;

    std::cout << first_in_array(
        array1, 1, array, 30
    ) << std::endl;

    std::cout << first_in_array(
        array2, 1, array, 30
    ) << std::endl;

    std::cout << std::endl;

    std::cout
        << "Searching for an array of capacity 2; "
        << "not found is 29:"
        << std::endl;

    std::cout << first_in_array(
        array3, 2, array, 30
    ) << std::endl;

    std::cout << first_in_array(
        array4, 2, array, 30
    ) << std::endl;

    std::cout << std::endl;

    std::cout
        << "Searching for an array of capacity 8; "
        << "not found is 23:"
        << std::endl;

    std::cout << first_in_array(
        array5, 8, array, 30
    ) << std::endl;

    std::cout << first_in_array(
        array6, 8, array, 30
    ) << std::endl;

    return 0;
}

/***************************************************
 * first_in_array
 *
 * Determine whether all the entries of array1
 * appear consecutively and in the same order
 * within array2.
 *
 * For example, given the array
 *
 *   index:   0    1    2    3    4
 *            5    6    7    8    9
 *
 *   entry: 100  101  102  103  104
 *          105  106  107  108  109
 *
 * the array
 *
 *     { 104, 105, 106 }
 *
 * occurs starting at index 4.
 *
 * The array
 *
 *     { 106, 107, 108, 109, 110 }
 *
 * does not occur.
 *
 * Similarly, { 107 } occurs at index 7, whereas
 * { 42 } does not occur.
 *
 * The empty array occurs trivially at index 0.
 *
 * If array1 is not found, return one beyond the
 * last index at which array1 could have started:
 *
 *     capacity2 - capacity1 + 1.
 *
 * If capacity1 > capacity2, array1 cannot possibly
 * occur within array2.
 ***************************************************/
std::size_t first_in_array(
    int         const array1[],
    std::size_t const capacity1,
    int         const array2[],
    std::size_t const capacity2
) {
    // Enter your implementation here.

    if ( capacity1 > capacity2 ) {
        return 0;
    }

    return capacity2 - capacity1 + 1;
}




































// Hint:
//
// You will need a loop that considers each possible
// starting index in array2. At each starting index,
// use another loop to determine whether all the
// corresponding entries of array1 and array2 match.
//
// For example, suppose array2 has capacity 12 and
// array1 has capacity 4:
//
//       0  1  2  3  4  5  6  7  8  9 10 11
//       *  *  *  *  *  *  *  *  *  *  *  *
//    0  *  *  *  *
//    1     *  *  *  *
//    2        *  *  *  *
//    3           *  *  *  *
//    4              *  *  *  *
//    5                 *  *  *  *
//    6                    *  *  *  *
//    7                       *  *  *  *
//    8                          *  *  *  *
//
// Thus, the possible starting indices are
//
//     0, 1, 2, ..., 8.
//
// There is no point in starting at index 9 because
// there are only three entries remaining in array2,
// while array1 contains four entries.
//
// In general, the number of possible starting
// indices is
//
//     capacity2 - capacity1 + 1.
//
// For each possible starting index, compare the
// entries of array1 with the corresponding entries
// of array2.
//
// As soon as two corresponding entries are
// different, you can stop checking that starting
// index and move on to the next one.
//
// If capacity1 is zero, what happens?
//
// At the first possible starting index, there are
// no entries that fail to match, so the empty array
// is found immediately at index 0.
//
// If capacity1 > capacity2, there are no possible
// starting indices at all.












































// One solution:

/*
std::size_t first_in_array(
    int         const array1[],
    std::size_t const capacity1,
    int         const array2[],
    std::size_t const capacity2
) {
    if ( capacity1 > capacity2 ) {
        return 0;
    }

    std::size_t const n_starts{
        capacity2 - capacity1 + 1
    };

    // Try each possible starting index in array2.
    for ( std::size_t k2{ 0 }; k2 < n_starts; ++k2 ) {
        // Assume this is a match until an unequal
        // pair of entries is found.
        bool found{ true };

        for ( std::size_t k1{ 0 };
              k1 < capacity1;
              ++k1 ) {
            if ( array1[k1] != array2[k2 + k1] ) {
                found = false;
                break;
            }
        }

        // If no unequal entries were found, this
        // is the first occurrence of array1.
        if ( found ) {
            return k2;
        }
    }

    return n_starts;
}
*/