Longest common substring

First we checkout the definition of problem:

the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.

For example, given ‘abcda’ and ‘bcdabc’, we should give ‘bcda’.

First trial – brute force

For this problem, we can easily come up with the brute force solution which compare substrings with same length like following:

max = 0
for i of s1[0, n]
    for j of s2[0, m]
        for l of [0, min(n-i, m-j)]
            if is_same(s1[i, i+l], s2[j, j+l])
                compare with max then set max
            else
                break

This works, but is also slow – with time complexity O(n * m * min(n, m)^2).

Or we make a little optimization by just comparing last char so we can achieve it with O(n * m * min(n, m)).

max = 0
for i of s1[0, n]
    for j of s2[0, m]
        for l of [0, min(n-i, m-j)]
            if is_same(s1[i+l], s2[j+l])
                compare with max then set max
            else
                break

Think again

Soon, we will notice, when we compare two substrings to see whether they are the same, we can tell the common substrings in them. So why don’t we make our code cleaner like following:

max = 0
for i of s1[0, n]
    for j of s2[0, m]
        common = get_common(s1[i, n], s2[j, m])
        compare with max then set max

In get_common, we can compare like original brute force way, which make sure this version is equivalent to the old way. But doesn’t get_common do similar thing with smaller problem size? Bingo, we will soon find a recursive solution.

Try again – dynamic programming

So, we now try to convert above solution into a recursive one:

get_common(i, j) {
    if i == 0 || j == 0
        return 0

    common = get_common(s1[0, i-1], s2[0, j-1])
    if s1[i] == s[j]
        return common + 1
    else 
        return ???

Before we finish the ‘???’ with the right answer, we will make sure our definition for ‘substring’ clear: it has to occupy consecutive positions in original string.
So for:

xxxab
   ↑
   i

xxxbb
   ↑
   j

if we invoke get_common(i, j) on them, it should return 0( if we return 3, get_common(i+1, j+1) will return 3 + 1, but that answer fails the definition of substring.)

The essence that we have to return 0 when character not match is two reasons:

• we want to infer common[i, j] from common[i-1, j-1]
• substring require consecutive characters. If last char not match, we can’t get common[i, j] from common[i-1, j-1].

So we may better call it get_common_end_here.

get_common_end_here(i, j) {
    if i == 0 || j == 0
        return 0

    common = get_common_end_here(s1[0, i-1], s2[0, j-1])
    if s1[i] == s[j]
        return common + 1
    else 
        return 0

So far, we have not improve the speed. But the recursive version leave the space for it.
We can save the get_common_end_here(i-1, j-1) to save the time of get_common_end_here(i, j).

Finally, we can use space of O(m*n), time of O(m*n) to get the answer.

for i in 0, n
    for j in 0, m
        if i == 0
            endHere[0][j] = (s1[0] == s2[j]) ? 1 : 0
            continue
        if j == 0
            endHere[i][0] = (s1[i] == s2[0]) ? 1 : 0
            continue
        if s1[i] != s[j]
            endHere[i][j] = 0
        else 
            endHere[i][j] = endHere[i-1][j-1] + 1

for i in 0, n
    for j in 0, m
        find max in endHere[i][j]

Advanced – suffix tree

If you don’t know suffix tree and you don’t have too much time or you are satisfied with the performance of DP version, you can just skip this section.

Introduction

You may have to refer to the following two long article to understand what is suffix tree (I prefer that stackoverflow question).

• stackoverflow: suffix tree explanation
• Wikipedia: suffix tree

Use

Now suppose we have a suffix tree implementation( it will be a complicate and hard job to do. Believe me. You can refer to my implementation in java which seems right), we can just add the string to tree and find the lowest common ancestor in O(n) time.

Conclusion

• As far as I can tell, dynamic programming is always used to solve the problem that requires a max/min value.
• In essence, dynamic programming is sacrificing memory for speed
• Dynamic programming is kind of divide and conquer
• When finding a special sub-array( like substring), the sub-problem of DP is always some condition end here in order to meet the requirement of consecutive position, which is different from sub-sequence.

Question

If we ask for longest common sequence, what ??? should be and how to invoke this function?

get_common(i, j) {
    if i == 0 || j == 0
        return 0

    common = get_common(s1[0, i-1], s2[0, j-1])
    if s1[i] == s[j]
        return common + 1
    else 
        return ???

Ref

• Wkipedia: longest common substring

Written with StackEdit.