String subscipt out of range

Question

My code, after being compiled in MS VS 2012, accepts input as it should, and then crashes with the following report:

Debug Assertion Failed!
...\include\xstring
Line:1662
Expression:string subscript out of range

The code is as follows:

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <time.h>


using namespace std;


const unsigned short MAX_STRINGS = 10;
const unsigned int  MAX_SIZE=10000;
vector<string> strings;
unsigned int len;

string GetLongestCommonSubstring( string string1, string string2 );
inline void readNumberSubstrings();
inline const string getMaxSubstring();

void readNumberSubstrings()
{
    cin >> len;

    assert(len > 1 && len <=MAX_STRINGS);

    strings.resize(len);

    for(unsigned int i=0; i<len;i++)
        strings[i]=string(MAX_SIZE,0);

    for(unsigned int i=0; i<len; i++)
        cin>>strings[i];
}

 const string getMaxSubstring()
{
    string maxSubstring=strings[0];
    long T=clock();
    for(unsigned int i=1; i < len; i++)
        maxSubstring=GetLongestCommonSubstring(maxSubstring, strings[i]);
    cout << clock()-T << endl;
    return maxSubstring;
}

string GetLongestCommonSubstring( string string1, string string2 ) 
{

    const int solution_size = string2.length()+ 1;

    int *x=new int[solution_size]();
    int *y= new int[solution_size]();

    int **previous = &x;
    int **current = &y;

    unsigned int max_length = 0;
    unsigned int result_index = 0;

    unsigned int j;
    unsigned int length;
    int J=string2.length() - 1;

    for(unsigned int i = string1.length() - 1; i >= 0; i--)
    {
        for(j = J; j >= 0; j--) 
        {
            if(string1[i] != string2[j]) 
                (*current)[j] = 0;
            else 
            {
                length = 1 + (*previous)[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }

                (*current)[j] = length;
            }
        }

        swap(previous, current);
    }
    string1[max_length+result_index]='\0';
    return &(string1[result_index]);
}

int main()
{
    readNumberSubstrings();
    cout << getMaxSubstring() << endl;
    return 0;
}

I guess it must be something really simple (like some loop condition or something like that) that causes it to crash, but I fail to see it.

Answer 1

Your problem is in using unsigned int. Look at this line:

for(j = J; j >= 0; j--)

Here, after j becomes 0, it gets decremented. But your j is unsigned, so instead of becoming -1 (and exiting the cycle on the next iteration), j becomes 4158584613, and the cycle continues, trying to access the obviously out-of-bonds element at index 4158584613 at this line:

(*current)[j] = 0;

Making i, j, and length signed will solve your problem.

Answer 2

I loaded it into test solution on my local Visual Studio 2008 and replaced unsigned int with int in i and j and it ran

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <time.h>


using namespace std;


const unsigned short MAX_STRINGS = 10;
const unsigned int  MAX_SIZE=10000;
vector<string> strings;
unsigned int len;

string GetLongestCommonSubstring( string string1, string string2 );
inline void readNumberSubstrings();
inline const string getMaxSubstring();

void readNumberSubstrings()
{
    cin >> len;

    assert(len > 1 && len <=MAX_STRINGS);

    strings.resize(len);

    for(unsigned int i=0; i<len;i++)
        strings[i]=string(MAX_SIZE,0);

    for(unsigned int i=0; i<len; i++)
        cin>>strings[i];
}

 const string getMaxSubstring()
{
    string maxSubstring=strings[0];
    long T=clock();
    for(unsigned int i=1; i < len; i++)
        maxSubstring=GetLongestCommonSubstring(maxSubstring, strings[i]);
    cout << clock()-T << endl;
    return maxSubstring;
}

string GetLongestCommonSubstring( string string1, string string2 ) 
{

    const int solution_size = string2.length()+ 1;

    int *x=new int[solution_size]();
    int *y= new int[solution_size]();

    int **previous = &x;
    int **current = &y;

    unsigned int max_length = 0;
    unsigned int result_index = 0;

    int j;
    unsigned int length;
    int J=string2.length() - 1;

    for(int i = string1.length() - 1; i >= 0; i--)
    {
        for(j = J; j >= 0; j--) 
        {
            if(string1[i] != string2[j]) 
                (*current)[j] = 0;
            else 
            {
                length = 1 + (*previous)[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }

                (*current)[j] = length;
            }
        }

        swap(previous, current);
    }
    string1[max_length+result_index]='\0';
    return &(string1[result_index]);
}

int main()
{
    readNumberSubstrings();
    cout << getMaxSubstring() << endl;
    return 0;
}

Thanks Niraj Rathi