-
Notifications
You must be signed in to change notification settings - Fork 0
/
EDIST.cpp
51 lines (51 loc) · 907 Bytes
/
EDIST.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
using namespace std;
char s[2010],str[2010];
int edist[2010][2010],n,m;
int min (int a,int b,int c)
{
if (a<b)
{
if (a<c)
return a;
return c;
}
else
{
if (b<c)
return b;
return c;
}
}
void Levdist ()
{
int i,j,edit;
for (j=0;j<=m;j++)
edist[0][j]=j;
for (i=1;i<=n;i++)
edist[i][0]=i;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
edit=1;
if (s[i-1]==str[j-1])
edit=0;
edist[i][j]=min (edist[i-1][j]+1,edist[i][j-1]+1,edist[i-1][j-1]+edit);
}
}
int main()
{
int t;
cin>>t;
while (t--)
{
cin>>s;
cin>>str;
n=strlen(s);
m=strlen(str);
Levdist();
cout<<edist[n][m]<<endl;
}
return 0;
}