Strings

String notation

Measures of similarity

LONGEST COMMON SUB-WORD

Longest common sequence

editing distance

LGTW algo

Teste alle relativen Positionierungen von s und s0 zueinander und bestimme jeweils das LGTW.

=>O((n+m) *n)

LGTS

-crossing free

-If both words end with the same character, then the following holds: |LGTS(s, s’)| = |LGTS(s_n-1; s’_m-1)|+ 1

-else: |LGTS(s, s’)| = max( |LGTS(s, s’_m-1)| , |LGTS(s_n-1, s’)| )

-as recursion tree algo: O(2^n+m); however it has repeated steps

-alternative: Store intermediate results that have already been calculated in a table. =>O(nm)

Editing Distance

Convert word s to word s0 as cheaply as possible. To do this, assign costs to the operations Insert, Delete, and Replace.

Costs are non-negative and uniform.

intersection-free assignment

• ED(s; ε) = |s|

• ED(s; s’) = ED(s’; s)

• ED(s; s’) >= m - n

-every permutation of answer is optimal solution

-mit recursion O(3^n+m)