Longest Substring required

[VJTechno]

write a program that will identify the longest substring in two given strings that is common to both.

[javaAddict]

Why should we write such program. I have no use for that, and I am not interested in finding the longest substring in two given strings that is common to both. Some things are better left unknown.

If you want to find the longest substring in two given strings that is common to both then show some effort by posting some code and ask your question in a better manner.

[WargRider]

Ok, well, first of all, yes you cannot go around REQUESTING code to be solved willy nilly, but I could help you out by saying that the Strings API has very easy to use and useful methods like String.splitString (I think forget the name though) and String.subString() which could REALLY help you. IF you have ONE long string, and a bunch of strings spereated by a delimiter , say "." you can literally break the String into a String array with the sub strings separated by the "."s . So:

Hello.World

Could become a String array of:

s[0] = "Hello";
s[1] = "World";

Good luck!

[VJTechno]

Thank You all for replying to this thread. More than need this was a curiosity driven question and was asked to me by an interviewer. i could solve it in similar way as the following:

for (int m = 0; m < str_.length(); m++) 
  {
    for (int n = 0; n < toCompare_.length(); n++) 
    {
      compareTable[m][n] = (str_.charAt(m) != toCompare_.charAt(n)) ? 0
          : (((m == 0) || (n == 0)) ? 1
              : compareTable[m - 1][n - 1] + 1);
      maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
          : maxLen;
    }

i was wondering if this is the most efficient way as it creates 'm x n' matrix and whole of which is not used efficiently ???

[tesuji]

write a program that will identify the longest substring in two given strings that is common to both.

Hi

LCS is a famous problem in programming. You my have a look at my posting there and follow the links you possibly will find solutions.

Be aware of that LCS isn't that easy to program. Poor solutions have time complexity of O(n^4), optimal solutions based on dynamic programming have O(n^2) or (O(mn)) in both time and storage.

-- tesu

[VJTechno]

WOW.. here is the solution - http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring... thanx to Mr. Tesuji :)