Longest Common Substring non-DP solution with O(m*n)

Question

The definition of the problem is:

Given two strings, find the longest common substring.

Return the length of it.

I was solving this problem and I think I solved it with O(m*n) time complexity. However I don't know why when I look up the solution, it's all talking about the optimal solution being dynamic programming - http://www.geeksforgeeks.org/longest-common-substring/

Here's my solution, you can test it here: http://www.lintcode.com/en/problem/longest-common-substring/

int longestCommonSubstring(string &A, string &B) {

    int ans = 0;
    for (int i=0; i<A.length(); i++) {
        int counter = 0;
        int k = i;
        for (int j=0; j<B.length() && k <A.length(); j++) {

            if (A[k]!=B[j]) {
                counter = 0;
                k = i;

            } else {
                k++;
                counter++;
                ans = max(ans, counter);

            }  
        }
    }

    return ans;        
}

My idea is simple, start from the first position of string A and see what's the longest substring I can match with string B, then start from the second position of string A and see what's the longest substring I can match....

Is there something wrong with my solution? Or is it not O(m*n) complexity?

The solution you are describing in words would be O(nm^2) if implemented correctly. That's why the DP solution is necessary. — augurar

Paul Hankin Paul Hankin · Accepted Answer · 2016-04-25T02:26:38

Good news: your algorithm is O(mn). Bad news: it doesn't work correctly.

Your inner loop is wrong: it's intended to find the longest initial substring of A[i:] in B, but it works like this:

j = 0
While j < len(B)
   Match as much of A[i:] against B[j:]. Call it s.
   Remember s if it's the longest so far found.
   j += len(s)

This fails to find the longest match. For example, when A = "XXY" and B = "XXXY" and i=0 it'll find "XX" as the longest match instead of the complete match "XXY".

Here's a runnable version of your code (lightly transcribed into C) that shows the faulty result:

#include <string.h>
#include <stdio.h>

int lcs(const char* A, const char* B) {
    int al = strlen(A);
    int bl = strlen(B);
    int ans = 0;
    for (int i=0; i<al; i++) {
        int counter = 0;
        int k = i;
        for (int j=0; j<bl && k<al; j++) {
            if (A[k]!=B[j]) {
                counter = 0;
                k = i;
            } else {
                k++;
                counter++;
                if (counter >= ans) ans = counter;
            }  
        }
    }
    return ans;        
}

int main(int argc, char**argv) {
    printf("%d\n", lcs("XXY", "XXXY"));
    return 0;
}

Running this program outputs "2".

Longest Common Substring non-DP solution with O(m*n)

2 Answers