# Dynamic programming table for finding similar substrings is too large

Substring Diff
Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}$. In set notation, $M(i, j, L)$ refers to the size of the set $\{0 \leq x < L \mid p_{i + x} \neq q_{j + x}\}$.

Given an integer $K$, your task is to find the maximum length $L$ such that there exists pair of indices $(i,j)$ for which we have $M(i, j, L) \leq K$. Of course, we should also have $i + L - 1 \leq n$ and $j + L - 1 \leq n$.

Constraints

• $0 \leq K \leq |P|$
• Both $P$ & $Q$ would have the same length
• The size of each of the string would be at the max 1500
• All characters in $P$ and $Q$ are lower-case English letters.

The recursive function will have the form:

longest(string1, string2, allowed_mismatches) =
{
... (something :P )
}


The state space then has size $K^3$. With an upper bound on $K$ of 1500, the running time and space usage will be terrible... So direct dynamic programming will not work without some additional property to reduce the state space.

Ideas?

UPDATE

Using the ideas suggested by both Yuval and Vor, I came up with the following solution that works like a charm, running in $O(K^2)$ time and using $K$ space.

def longest_range_min_sum(str1, str2, start1, start2, slice_size, max_sum):
longest = 0
i = 0
running_sum = 0
while i + longest < slice_size:
if str1[start1 + i + longest] != str2[start2 + i + longest]:
running_sum += 1
if running_sum > max_sum:
if str1[start1 + i] != str2[start2 + i]:
running_sum -= 1
i += 1
else:
longest += 1
return longest

import sys

num_cases = int(data.pop(0))
for ignore in xrange(num_cases):
max_mismatches, str1, str2 = data.pop(0).split()
max_mismatches = int(max_mismatches)
m = n = len(str1)
longest = 0
for i in xrange(m + n + 1):
if i > n:
slice_size = m - (i - n)
else:
slice_size = min(i, m)
if slice_size == 0:
continue
end1 = max(m, m - i)
if i > n:
end1 = m - (i - n)
start1 = end1 - slice_size
end2 = min(i, n)
start2 = end2 - slice_size
#print zeros_and_ones
#print str1[start1:end1], ' - ', str2[start2:end2]
longest_in_sub = longest_range_min_sum(str1, str2, start1, start2, slice_size, max_mismatches)
#print longest_in_sub
longest = max(longest, longest_in_sub)
print longest

• If you have to copy&paster contest problems here, please restrict yourself to the essentials and link the source. "the recursion above will fail" is not a very meaningful statement; I'm sure the solution is well-defined, you just run out of memory (?).
– Raphael
Oct 10 '12 at 20:03
• Yep, run out of memory. Don't have 1500^3 ~ 2^30 bytes of ram free... Oct 12 '12 at 15:03
• Did you run out of heap or was it a stack overflow? Oct 15 '12 at 7:38

One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.

What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The sequence in question is $J_1 = I_1 - I_0,\ldots,J_{t+1}=I_{t+1}-I_t$. Every $K+1$ consecutive numbers $J_a,\ldots,J_{a+K}$ correspond to a maximal solution for your problem of length $J_a + \cdots + J_{a+K} - 1$. The entire algorithm takes linear time.

Edit: This calculates the maximal $L$ such that $M(i,i,L) \leq K$ for some $i$. The actual problem wanted to find the maximal $L$ such that $M(i,j,L) \leq K$ for some $i,j$. By considering all possible shifts, we can solve this in $O(N^2)$ time and $O(K)$ space.

• Hello Yuval. Can you explain how the reduction works? Oct 12 '12 at 6:21
• The basic idea is that (up to endpoints) the optimal solution is maximal, in the sense that it is bordered by mismatch on both sides. So it is enough to consider stretches starting and ending with a mismatch, and having $K$ mismatches inside. The length of the stretch is related to the distance between each mismatch and the one following it. This is captured by the sequence $J$. Now you form the appropriate optimization problem, and it turns out that it can be solved very efficiently. Oct 12 '12 at 18:20
• But what is the reduction algorithm? How do I transform strings P and Q into one sequence? Oct 12 '12 at 21:33
• You calculate the positions of the mismatches $I$, and from them you construct the sequence $J$. If you're careful, you can run the entire algorithm with memory $O(K)$. Oct 12 '12 at 23:26
• But then don't you have to calculate the position of the mistakes for every combination of P[i:] and Q[j:]? Then for each combination i and j, you'd create the sequence you mentioned. But then running time is O(K^3), too large with a bound of 1500 on K. Oct 14 '12 at 13:45

Using Yuval's reduction, the problem can be reformulated as "Find the largest range $(i,j)$ in a binary string $S \in \{0,1\}^*$ such that the number of $1$s contained in the range is $\leq K$" (see this question).

The idea is to start with an initial valid range $(0,j)$ of length $maxlen$ and then shift the "window" $(i,i+maxlen)$ to the right, checking at every step if maxlen can be increased.

This is the pseudocode of a possible solution:

 INPUT : string P and Q of length n, integer K
// string indexes are 0 based (P[0] = first char of P)
maxidx = 0   // position of the largest interval
maxlen = 0   // length of the largest interval
i = 0        // current position of the "window" (i,i+maxlen)
diffsum = 0  // sum of the mismatches in the range (i,i+maxlen)
while ( i + maxlen < n ) do
// update the number of mismatches of the window:
if (P[i + maxlen] != Q[i + maxlen]) then diffsum = diffsum + 1
if diffsum <= K
then begin
maxlen = maxlen + 1 // expand window
maxidx = i  // update base pointer
end
else begin
if (P[i] != Q[i]) then diffsum = diffsum - 1 // discard mismatches out of the window
i = i + 1 // shift window to the right
end

OUTPUT : if maxlen > 0
then output (maxidx, maxidx + maxlen - 1) // output the largest interval
else output("no range with # of mismatches <= K")


Time complexity: $O(n)$, space $O(1)$.

• But this assumes that the longest range must start at the same position for both strings P and Q, when in fact if you look at the problema statement, the longest range can be P[i, length], Q[j, length]. Oct 15 '12 at 9:54
• @Alexandre: you are right I quickly posted the answer which works well with the other question "Longest range with sum smaller than K", without looking at the details of this one :-( ... I'll try to fix it later (or move this answer to the other question :)
– Vor
Oct 15 '12 at 10:42
• @Alexandre: you can use iterate an index $j$ in $[0..n-maxlen-1]$ and call the above function (change the two ifs to: "... P[i + maxlen] != Q[j + maxlen] ..." and "...P[i] != Q[j]..."). The complexity increases to $O(n^2)$. Do you need the details?
– Vor
Oct 15 '12 at 16:40
• I gave the answer to Yuval because he had the insight that solved the problem, though I think you expressed his ideas in a much more didactic manner. Wish I could award you points as well. I upvoted your answer. Thanks! Oct 19 '12 at 7:05