Classical algorithms for computing the similarity between two sequences use a dynamic programming matrix, and compares two strings of size $n$ in $O(n^2)$ time. We address the challenge of computing the similarity of two strings in sub-quadratic time, for metrics which use a scoring matrix of unrestricted weights. Our algorithm applies to both local and global similarity computations. The speed-up is achieved by using the Lempel-Ziv parsing of both strings. It leads to an $O(hn^2/\log n)$ algorithm for an input on a constant-size alphabet, where $h\lt 1$ is the entropy of strings.