Levenshtein distance

[1vf9z8AR]

Problem-
https://www.spoj.com/problems/EDIST/

I am using Levenshtein distance to find the edit distance. I am not able to find why I am getting the wrong answer in spoj.

  #include<iostream>
using namespace std;
int arr[4000][4000];
int minimum(int a,int b,int c)
{
    if(b<=a && b<=c)
        return b;
    else if(c<=a && c<=b)
        return c;
    else
        return a;
}
int main()
{
    arr[0][0]=0;
    for(int i=1;i<=2000;i++)
        arr[i][0]=i;
    for(int j=1;j<=2000;j++)
        arr[0][j]=j;
    int test;
    cin>>test;
    cin.ignore();
    while(test>0)
    {
        string a,b;
        getline(cin,a);
        getline(cin,b);
        int row=a.size(),col=b.size();
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                if(a[i-1]==b[j-1])
                    arr[i][j]=arr[i-1][j-1];
                else
                    arr[i][j]=minimum(arr[i-1][j],arr[i][j-1],arr[i-1][j-1])+1;
            }
        }
        cout<<arr[row][col]<<endl;
        test--;
    }
    return 0;
}

[salem c]

Well you don't re-initialise your arr between test cases.

Assuming that your algorithm is otherwise correct.

[keskiverto]

The first row and column of the matrix are never modified within the algorithm.
Re-initialization is thus unnecessary.
See https://www.cuelogic.com/blog/the-levenshtein-algorithm

The simple test cases yield expected result.


You don't need 4000*4000 matrix and it does not need to be global. That should not affect the result though.

[1vf9z8AR]

But what is the issue?
I did those things to reduce run time.

[1vf9z8AR]

bump