- The edit distance between S1 and S2 is the minimum number of deletions, insertions and substitutions needed to transform S1 to S2.

- |S1|=m, |S2|=n

- D(i,j) is the edit distance between S1[1..i] and S2[1..j].

- Recurrence relation:
- basis:

Previous slide | Next slide | Back to first slide | View graphic version |