# String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a substring of $T$, except that I have a more relaxed notion of when two characters match.

Two characters in these strings are similar if $|Q[j] - T[l]|\leq 1$. Call the indices $i,j$ a good pair if $|Q[j] - T[j+i-1]|\leq 1$, that is if the characters in the $j+i-1$'s cell in $T$ and the $j$'s cell in $Q$ are similar. An index $i$ is good for all if for all $1\leq j \leq k$, the pair $i,j$ is a good pair.

I'd like to find all the good-for-all indices. That is, I aim to find all the indices $1\leq i\leq n$ s.t. for all $1\leq j \leq k$, we have $|Q[j] - T[j+(i-1)]|\leq 1$.

I'm at a loss even where should I begin from. Obviously I can solve naively, but this is not interesting at all. I'm not even sure what should be the optimal time for this problem. Also, I don't see any lower bound on the running time (except $O(n)$ obviously).

How efficiently can we find all the good-for-all indices? What algorithm can I use for this?

• Have you tried generalizing a DFA-based algorithm like KMP? – Yuval Filmus Feb 5 '16 at 14:27
• 1. Do you really intend $|\Sigma|=|T|$? Or should you use two different variables for $|\Sigma|$ and $|T|$? Can you edit the question accordingly? 2. Have you tried convolution-based methods, e.g., using FFT? – D.W. Feb 5 '16 at 17:28
• Also, can you tell us how the parameters $k,n,|\Sigma|$ relate? For instance, if $k<n$ and $k < |\Sigma|/2$, then there are some algorithms that become possible that wouldn't be possible otherwise. – D.W. Feb 5 '16 at 21:34

You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching).

This particular problem can be solved efficiently using convolution methods. The running time will be something like $O(n \lg n)$, times some small factors. Let me outline the algorithm, and then explain why it works.

# The algorithm

Step 1: We will construct binary strings $T' \in \{0,1\}^{6n}$, $Q' \in \{0,1\}^{6k}$, with a special property:

• If index $i$ is good-for-all, then there are $\ge k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.

• If index $i$ is not good-for-all, then with probability at least $1/2$, there are $< k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.

Let me outline how to construct $T',Q'$. First, pick a random hash function $h:\Sigma \to \{1,2,\dots,6\}$. Next, define a code $C_T:\Sigma \to \{0,1\}^6$ like this: $C_T(x)$ is a 6-bit string that is 1 at index $h(x)$ and 0 at all other positions. Also, define a code $C_Q:\Sigma \to \{0,1\}^6$ as follows: $C_Q(x)$ is a 6-bit string that is 1 at indices $h(x)$, $h(x-1)$, and $h(x+1)$, and 0 at all other positions.

Finally, define the binary string $T'$ to be the concatenation of codewords

$$T' = C_T(T) C_T(T) \cdots C_T(T[n-1]),$$

and similarly $Q'$ to be the concatenation of codewords

$$Q' = C_Q(Q) C_Q(Q) \cdots C_Q(Q[k-1]).$$

You can check that these two strings satisfy the properties above.

Step 2: We will use convolution (polynomial multiplication) to find all indices that are good-for-all. Define polynomials $T(x),Q(x)$ from the binary strings $T',Q'$ as follows:

\begin{align*} T(x) &= \sum_j T'_j x^j\\ Q(x) &= \sum_j Q'_j x^{6k-1-j} \end{align*}

Multiply these two polynomials to get the polynomial $P(x) = T(x) Q(x)$. Let $p_i$ be the coefficient of $x^i$ in $P(x)$, so that $P(x) = \sum_i p_i x^i$.

We have the following nifty property: $p_{6k-1-6i}$ counts the number of indices $j$ where both $T'_{j}$ and $Q'_{j+6i}$ are 1. Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all". Every index that is actually good-for-all will appear in that set, and every non-good-for-all index has at most a probability $1/2$ of appearing in the set of "suggested" indices.

Step 3: Repeat Steps 1 and 2 80 times, and keep only those indices that are suggested in every iteration. Output that list.

# Correctness

All of the good-for-all indices will remain and appear in the output. Also, there's at most a $n/2^{80}$ probability that any non-good-for-all index survives all 80 iterations. This probability is small enough as to be negligible.

# Running time

The running time of this algorithm is dominated by the time to multiply two polynomials of degree $6n,6k$. Assuming $n \ge k$, this running time is basically $O(n \lg n)$ (ignoring log-log factors) using standard techniques.

In practice there are a number of ways one could optimize this further. For instance, we can often stop early without doing all 80 iterations: once the set of surviving suggested indices is small enough, we can just check each one directly and output only the correct ones.

# Other approaches

Since your problem is a generalization of string matching, you could also look at other algorithms for string matching and see if any of those techniques can be generalized to your situation. For instance:

• It would be straightforward to adapt finite automaton based search methods: you can build an automaton based on $Q$ that accepts all strings that would match $Q$ as a substring (where "match" allows two similar characters to be treated as matching). Building such a DFA might be very slow, but once you have the DFA, testing whether $T$ is a match can be done very fast -- in linear time.

• It might be possible to adapt the Knuth-Morris-Pratt algorithm to your situation. It might take some thought to work out the details, but if it works out, you might get a linear-time algorithm, i.e., $O(n)$ running time.

• Also, take a look at Boyer-Moore.

I would especially suggest you take a look at KMP -- it looks plausible to me that this might yield a viable algorithm.

• You said: "....$p_{6k-1-6i}$ counts the number of indices $j$ where both $T^{′}_j$ and $Q^{'}_{j+6i}$ are $1$. Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all"." But when searching for a good-for-all index, we wanted something else, that is, we wanted $| Q_j -T_{j+i-1}| \leq 1$ and yet when constructing $T'$ and $S'$ you said: "....If index ii is good-for-all, then there are ≥$k$ indices$j$ where both $T′_j$ and $Q′_{j+6i}$ are $1$." I do not understand where did $6i$ pop from? Why $6n$ and $6k$ and not simply $n$ and $k$? – Eric_ Feb 12 '16 at 15:17
• @Eric_, the factor of 6 comes from the fact that the code encodes one character to 6 bits. This means that the $i$th character corresponds to bits $6i .. 6i+5$. I didn't check all of the index carefully just now, but that's the intuition. Put another way: work through the construction, and work out what the length of $T'$ and $Q'$ are in bits. You'll find they are $6n$ and $6k$ bits long, respectively, not $n,k$ bits. – D.W. Feb 12 '16 at 17:38
• Could you clarify why the strings $T'$ and $Q'$ you have built hold the properties we want them to hold? They seem kind of random to me, as they only depend on the hash function $h$, which is random. – Eric_ Feb 15 '16 at 20:15
• @Eric_, try and work through an example! I think maybe you'll see what's going on if you work through an example, and I think that'll be more effective than any explanation I can provide. They're not random. They depend on both $h$ and on $T,Q$, and they do have some patterns -- they're not totally random. – D.W. Feb 16 '16 at 0:23
• I'm sorry, I tried for several times, but I do not see a way I can prove it. It seems $T'$ and $Q'$ are just depending on $h$, which is random! I don't see where is the usage of "similar"? (that is, having the difference between $Q_j$ and $T_{j+i-1}$ be $\leq 1$?) I just dont couldn't see how to find a prove for that.. – Eric_ Feb 22 '16 at 21:49