CODEWITHSUNDEEP
c++arrays
I Like
I Like

Reputation: 1847

What cause this array value to change?

I am going slightly crazy over a value changing in a multidimensional array even though assignment doesn't appear to happen. I am working on a program to find the longest common subsequence between two strings. To that end, I create an array of arrays whose dimensions are the lengths of the respective strings. I initialize the first row and column of the array to zeroes, but for some reason arr[2][0] becomes 1. This happens in the first iteration of the outer for loop when j=0 and k=5. 

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    string a = "bird";
    string b = "turdbi";
    int aLen = a.length();
    int bLen = b.length();
    int arr[aLen][bLen];
    //initializing the multidimensional array
    for (int i=0;i<aLen;i++){
        arr[i][0]=0;
    }
    for (int i=0;i<bLen;i++){
        arr[0][i]=0;
    }
    int subsequence=0;
    for (int j=0;j<aLen;j++){ //(0,0) is the leftmost corner of the table, to compensate for additional row/col
        for(int k=0;k<bLen;k++){
            if (a.at(j)==b.at(k)){
                subsequence = arr[j][k]+1; //add one to upper diagonal
            }
            else {
                subsequence = max(arr[j+1][k],arr[j][k+1]); //find max value from adjacent cells'
            }
            //how does arr[2][0] ==1??
            arr[j+1][k+1]=subsequence;
        }
        cout << endl;
    }

    return 0;
}

Upvotes: 0

Views: 72

Answers (1)

Jay Wai Tan
Jay Wai Tan

Reputation: 179

The comments basically said it all. Your index are out of bounds when you do j + 1 and k + 1 when your limits for j < aLen and k < bLen.

As for why it happens, arrays are guaranteed to be stored sequentially in the memory. Hence when you create an array -> int a[2][3], what you are creating in the memory is this.

0 - a[0][0] -   
1 - a[0][1]  |--- a[0] == &a[0][0] (same type, same value)
2 - a[0][2] -
3 - a[1][0] -
4 - a[1][1]  |--- a[1] == &a[1][0] (same type, same value)
5 - a[1][2] -

&a[0][0], &a[0][1], &a[0][2], &a[1][0]... are pointers to int. Hence every time the second subscript is incremented (in your case, k), we increment the pointer values by sizeof(int).

&a[0] and &a[1] are pointers to an array of 3 ints. Meaning, every time the first subscript is incremented (in your case j), we increment the pointer values by sizeof(int) * 3 because we are offsetting the address by 3 ints.

Hence by doing a[0][4], we will be editing values from a[1][1]. In the backend, the subscript operator is simply the compiler generating the offset for you.

Upvotes: 2

Related Questions