Identifying Syntactic differences Between Two ProgramsIdentifying Syntactic differences Between Two ProgramsYang, Wuu1991
Paper summaryjoecohenThis is a dynamic programming algorithm known as *Simple Tree Matching*:
```
int simple_tree_match(a,b){
if (a != b) return 0
m = the number of first-level sub-trees of a
n = the number of first-level sub-trees of b
M[i,0] := 0 for i = 0,...,m
M[0,j] := 0 for j = 0,...,n
for(i := 1 to m){
for(i := 1 to n){
x := M[i,j-1]
y := M[i-1,j]
z := M[i-1,j-1]+ simple_tree_match(a_i,b_j)
M[i,j] = max(x,y,z)
}
}
}
return M[m,n] + 1
}
```
This is a dynamic programming algorithm known as *Simple Tree Matching*:
```
int simple_tree_match(a,b){
if (a != b) return 0
m = the number of first-level sub-trees of a
n = the number of first-level sub-trees of b
M[i,0] := 0 for i = 0,...,m
M[0,j] := 0 for j = 0,...,n
for(i := 1 to m){
for(i := 1 to n){
x := M[i,j-1]
y := M[i-1,j]
z := M[i-1,j-1]+ simple_tree_match(a_i,b_j)
M[i,j] = max(x,y,z)
}
}
}
return M[m,n] + 1
}
```