5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you tried generalizing a DFA-based algorithm like KMP? $\endgroup$ – Yuval Filmus Feb 5 '16 at 14:27
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 5 '16 at 17:28
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 5 '16 at 21:34
3
$\begingroup$

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[0]) C_T(T[1]) \cdots C_T(T[n-1]),$$

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

$$Q' = C_Q(Q[0]) C_Q(Q[1]) \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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Eric_ Feb 12 '16 at 15:17
  • $\begingroup$ @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. $\endgroup$ – D.W. Feb 12 '16 at 17:38
  • $\begingroup$ 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. $\endgroup$ – Eric_ Feb 15 '16 at 20:15
  • $\begingroup$ @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. $\endgroup$ – D.W. Feb 16 '16 at 0:23
  • $\begingroup$ 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.. $\endgroup$ – Eric_ Feb 22 '16 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.