One can compute the Lenvenshtein distance of strings of many

One can compute the Lenvenshtein distance of strings of many GBs by noticing that only val[m][n] needs to be returned. There is no need to keep the entire val array in memory. Rather than considering each entry of the matrix as a task to execute, blocking the matrix helps having more work per task.

Need help with this assignment. Thank you

C++

1 Levenshtein Distance The levenshtein distance is used to compute the distance between two strings s1 and s2 of length n and m. int levenshtein (int n, char s1 [], int m, char s2] int va) Sequentially it is computed as: [0][0] = 0; val [0] [ i] = 0; val for (int i=1; i

Solution

//Lenvenshtein distance of strings using c++

#include <iostream>
using namespace std;
#include <stdio.h>
#include <math.h>
#include <string.h>
int d[100][100];
#define MIN(x,y) ((x) < (y) ? (x) : (y))
int main()
{
int i,j,m,n,temp,tracker;
char s[] = \"Alphabet\";
char t[] = \"Numbers\";
m = strlen(s);
n = strlen(t);

for(i=0;i<=m;i++)
d[0][i] = i;
for(j=0;j<=n;j++)
d[j][0] = j;

for (j=1;j<=m;j++)
{
for(i=1;i<=n;i++)
{
if(s[i-1] == t[j-1])
{
tracker = 0;
}
else
{
tracker = 1;
}
temp = MIN((d[i-1][j]+1),(d[i][j-1]+1));
d[i][j] = MIN(temp,(d[i-1][j-1]+tracker));
}
}
printf(\"the Levinstein distance is %d\ \",d[n][m]);
return 0;
}