Locality-Sensitive Hashing I

We can create two sets $S_S$ and $S_T$ by generating $k$-shingles for the strings $S$ and $T$, respectively. Then we can calculate the intersection $S_I$ and union $S_U$ between the two sets. Finally, we need to divide the length of $S_I$ by the length of $S_U$.

Complexity: $O(|S|\times |T|)$