Publikace na Matematicko-fyzikální fakulta |
2005
Abstrakt
Pro řetězec $A=a_1\ldots a_n$, převrácení $\rho(i,j)$, $1\leq i lt j\leq n$, otočí pořadí symbolů v podřetězci $a_i\ldots a_j$. Pro dva dané řetězce $A$ and $B$, problém srovnání pomocí převracení spočívá v nalezení nejmenšího počtu převrácení nutných pro transformaci $A$ na $B$.
Tradičně byl problém studován pro permutace. Zde uvažujeme zobecnění problému, kde se každý symbol smí opakovat k-krát v každém řetězci.
Hlavním výsledkem článku je $\Theta(k^2)$-aproximační algoritmus běžíc í v čase $O(kn)$.