Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsString similarity

Edit distance alignment

Running time and memory consumptions

Report a typo

Assume that for two strings $s$ and $t$ a table of intermediate answers is already calculated. Then, the sequence of edit operations transforming $s$ into $t$ can be reconstructed in ... time using ... additional memory (select all correct combinations).

Select one or more options from the list

O(|s| \cdot |t|), O(1)

O(|s| + |t|), O(min(|s|, |t|))

O(min(|s|, |t|)), O(|s| \cdot |t|)

O(|s| + |t|), O(|s| \cdot |t|)

___

Create a free account to access the full topic