UVA 1207 - AGTC(cpp file)

Problem Type : DP (Levenshtein Distance)


#include<stdio.h>
#include<algorithm>
#include<string.h>
#define MAX 1502
using namespace std;
int arr[MAX][MAX],len1,len2;
void labistine(char s[],char des[],int len1,int len2)
{
    int i,j;
    for(i=1;i<len1;i++)
    {
        for(j=1;j<len2;j++)
        {
           if(s[i]==des[j])
           {
               arr[i][j]=arr[i-1][j-1];
           }
           else if(s[i]!=des[j])
           {
              int p=min(arr[i-1][j]+1,arr[i][j-1]+1);
              arr[i][j]=min(arr[i-1][j-1]+1,p);
           }
        }
    }
}
void init()
{
    int i,j;

        for(j=0;j<len2;j++)
        {
            arr[0][j]=j;
        }
        for(i=0;i<len1;i++)
        {
            arr[i][0]=i;
        }

}
int main()
{
    int i,j;
    char source[MAX],des[MAX];
    while(scanf("%d ",&len1)==1)
    {
        source[0]='a';
        for(i=1; i<=len1; i++)
        {
            scanf("%c",&source[i]);
        }
        len1+=1;
        source[len1]='\0';
        des[0]='a';
        scanf("%d ",&len2);
        for(i=1; i<=len2; i++)
        {
            scanf("%c",&des[i]);
        }
        len2+=1;
        des[len2]='\0';
        init();
        labistine(source,des,len1,len2);
        printf("%d\n",arr[len1-1][len2-1]);
        memset(arr,0,sizeof(arr));
    }
}