6
votes
Accepted
Min Hamming distance of a given string from substrings of another string
Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:
Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.
Define polynomials $$p(x,y) = \sum_{i \...
- 2,793
5
votes
Accepted
Axioms for Shortest Paths
I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper that I might as well share. I hope the combination of thread ...
- 2,333
4
votes
Accepted
Are there Similar Distance Binary Error Correcting Codes?
Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.
To see it, write the elements of the set as the rows of ...
- 5,290
4
votes
Property testing in other metrics?
The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations ...
- 4,381
3
votes
Min Hamming distance of a given string from substrings of another string
Hint: Express the binary vectors as a polynomial with coefficients in {-1,0,1} and obtain the hamming distance of u with all length k contiguous subsequences of v through a polynomial multiplication.
...
- 131
1
vote
How to calculate this string-dissimilarity function efficiently?
For anyone interested:
I implemented The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan. It essentially approximates the described metric in linear time.
- 163
Only top scored, non community-wiki answers of a minimum length are eligible