Timeline for Efficient algorithm for a distance on strings
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 9, 2022 at 20:24 | comment | added | Andreas Haupt | Thanks, dvitek, dynamic programming was a good call. The only think I don't see is how to make it quadratic (and not cubic): I thought that one needs to go trough the matched index of k = n downto 1 and the one for k+1 (which would be stored). That would give cubic time. | |
| Dec 28, 2021 at 2:32 | history | edited | Andreas Haupt | CC BY-SA 4.0 |
added 44 characters in body
|
| Dec 27, 2021 at 20:55 | history | edited | YCor | CC BY-SA 4.0 |
formatting, added tag
|
| Dec 27, 2021 at 16:05 | comment | added | LSpice | What does "two sequences $[n]$, $[m]$" mean? As written, your definition seems very specific to (I assume you mean, or maybe you prefer to shift by $1$) $[n] = \{0, \dotsc, n - 1\}$ and $m = \{0, \dotsc, m - 1\}$; do you really mean it to apply to arbitrary sequences? | |
| Dec 27, 2021 at 16:03 | comment | added | dvitek | As you've written it this is not a metric, because the minimum always occurs when $E$ is empty. Assuming the definition you probably meant to write (namely, adding the condition that the projections of $E$ onto $[n]$ and $[m]$ are surjective) it is straightforward to write down a dynamic-programming approach to compute $\tilde{d}$ that is quadratic in $\max(m,n)$. So the only interesting question in this post is for what metrics you can approximate this in sub-quadratic time; this may be more suitable for cstheory.SE. | |
| Dec 27, 2021 at 15:38 | history | asked | Andreas Haupt | CC BY-SA 4.0 |