1

¡Hello!

I'm trying to find the longest common substring between two strings with a good time and space complexity, following using dynamic programming. I could find a solution with O(n^2) time and space complexity:

public static String LCS(String s1, String s2){
    int maxlen = 0;            // stores the max length of LCS      
    int m = s1.length();
    int n = s2.length();
    int endingIndex = m;  // stores the ending index of LCS in X

    // lookup[i][j] stores the length of LCS of substring
    // X[0..i-1], Y[0..j-1]
    int[][] lookup = new int[m + 1][n + 1];

    // fill the lookup table in bottom-up manner
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // if current character of X and Y matches
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
            {
                lookup[i][j] = lookup[i - 1][j - 1] + 1;

                // update the maximum length and ending index
                if (lookup[i][j] > maxlen)
                {
                    maxlen = lookup[i][j];
                    endingIndex = i;
                }
            }
        }
    }

    // return Longest common substring having length maxlen
    return s1.substring(endingIndex - maxlen, endingIndex);

}

My question is: How can I get better space complexity?

Thanks in advance!

NoobyProgrammer
  • 11
  • 4
  • 1
    How do you know it's possible to get O(n) time? What is your source? Answer that and you are already half way to answering your question. – smac89 Jun 14 '18 at 18:36
  • It is a duplicate question. See: https://stackoverflow.com/questions/3003372/longest-common-subsequence – Oz Molaim Jun 14 '18 at 18:49
  • No it is not. I'm asking about common substring space complexity and that question is asking about common subsequence time complexity – NoobyProgrammer Jun 14 '18 at 18:51

1 Answers1

0

The best time complexity you can get for finding the LCS of two Strings is O(n^2) using dynamic programming. I tried to find another algorithm for the problem since it was one of my University projects. But the best thing I could find was an algorithm with O(n^3) complexity. The main solution of this problem uses "Recurrence relation" which uses less space but far more process. But like "Fibonacci series" computer scientists used dynamic programming to reduce the time complexity. The Recurrence relation code:

void calculateLCS(string &lcs , char frstInp[] , char secInp[] , int lengthFrstInp ,  int lengthSecInp) {

if (lengthFrstInp == -1 || lengthSecInp == -1)
    return;

if (frstInp[lengthFrstInp] == secInp[lengthSecInp]) {
    lcs += frstInp[lengthFrstInp];
    lengthFrstInp--;
    lengthSecInp--;
    calculateLCS(lcs, frstInp, secInp, lengthFrstInp, lengthSecInp);

}


else {

    string lcs1 ="";
    string lcs2 ="";    
    lcs1 = lcs;
    lcs2 = lcs;
    calculateLCS(lcs1, frstInp, secInp, lengthFrstInp, lengthSecInp - 1);
    calculateLCS(lcs2, frstInp, secInp, lengthFrstInp - 1, lengthSecInp);

    if (lcs1.size() >= lcs2.size())
        lcs = lcs1;
    else
        lcs = lcs2;

}
Ark1375
  • 13
  • 5