The following is my code for Edit Distance problem. The problem asks us to find the edit distance between two strings.
My code, I think gives the correct output. If I run the code with two strings of 1500 length each, I get the error. But if I run it when one is say 1500 and the other is 1000 characters long, the program works fine. I can't understand why I am getting seg fault. I don't think I'm accessing any unwanted area. Please help.

#include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main()
{
    int z,t;
    cin>>t;
    for(z=0;z<t;z++)
    {
        int i,j;
        string a,b;
        cin>>a;
        cin>>b;
        int table[a.length()][b.length()];
        for(i=0;i<=a.length();i++)
            table[i][0]=i;
        for(i=0;i<=b.length();i++)
            table[0][i]=i;
        for(i=1;i<=a.length();i++)
        {

            for(j=1;j<=b.length();j++)
            {
                int min=10000;
                if(table[i][j-1]+1 < min)
                    min=table[i][j-1]+1;
                if(table[i-1][j]+1<min)
                    min=table[i-1][j]+1;
                if(a[i-1]==b[j-1] && (table[i-1][j-1]<min))
                    min=table[i-1][j-1];
                else if(a[i-1]!=b[j-1]&&(table[i-1][j-1]+1<min))
                    min=table[i-1][j-1]+1;
                table[i][j]=min;
            }
        }
        /*for(i=0;i<=a.length();i++)
        {
            for(j=0;j<=b.length();j++)
                cout<<table[i][j]<<" ";
            cout<<endl;
        }*/
        printf("%d\n",table[a.length()][b.length()]);
    }
    return 0;
}

The program is attempting to access non-existant table values. Lets assume a.length() == 10, then when i == 10 the statement table[i][0] is out-of-bounds because there is no element table[10][0]. Arrays are numbered 0 to but not including the upper-bounds of the array, in this case 0 1, 2, 3, 4, 5, 6, 7, 8, and finally 9. There is no 10th element. If you say your program works with 1000 then it works only by coincidence, not because its correct.

Edited 4 Years Ago by Ancient Dragon

@Ancient Dragon
I'm really sorry but I posted the wrong version of my code.
I was fiddling with the size of the table and posted the one with a.length aand b.length as dimensions.
In the actual code, the dimensions are indeed a.length()+1 and b.length()+1.
I am still getting seg fault. The problem is somewhere else. As I said I am getting correct answer for 1500 and 1000 length strings.
Sorry again for the inconvenience.

I made the table static and the program worked. Thanks for your help though.

This question has already been answered. Start a new discussion instead.