?
Solved

How to get the longest common substring of two strings?

Posted on 2011-05-10
31
Medium Priority
?
1,192 Views
Last Modified: 2012-08-14
Hey,

       I'm trying to use dynamic programming to get the longest common substring from two strings... this is what I got so far...

 
#include <iostream>
using namespace std;

void makeTable(string, string);
void print(int tableVals[][], int out, int in);

int main (int argc, const char * argv[])
{

    string firstString;
    string secondString;
    
    cout << "Enter the first string: ";
    cin >> firstString;
    cout << "Enter the second string: ";
    cin >> secondString;
    
    cout << "You have entered " << firstString << " as your first string, and " << secondString << " as your second string." <<endl;
    
    cout << firstString << " is " << firstString.length() << " long." <<endl;
    cout << secondString << " is " << secondString.length() << " long." <<endl;
    
    
    if(firstString.length() < secondString.length())
        makeTable(firstString, secondString);
    else
        makeTable(secondString, firstString);
    return 0;
}

void makeTable(string s1, string s2){
    int tableVals[s1.length()][s2.length()];
    int rowSum[s1.length()];
    int colSum[s2.length()];
    int tempx = 0;
    int tempy = 0;
    int temp = 0;
    int min = 0;
    int max = 0;
    int startIndex = 0;
    int endIndex = 0;
    
    //Initialize rowSum
    for(int x = 0; x < s1.length(); x++){
        rowSum[x] = 0;
    }
    
    //Initialize colSum
    for(int x = 0; x < s2.length(); x++){
        colSum[x] = 0;
    }
    
    //Build the table
    for(int i=0; i<s1.size(); i++){
        for(int j=0; j<s2.size(); j++){
            if(s1[i] == s2[j])
                tableVals[i][j] = 1;
            else
                tableVals[i][j] = 0;
        }
    }
    
    //Print the table
    for(int x = 0; x < s1.length() ; x++){
        for(int y = 0; y < s2.length() ; y++){
            cout << tableVals[x][y];
        }
        cout << endl;
    }
    
    //Calculate the rowSum
    for(int x = 0; x < s1.length(); x++){
        for(int j = 0; j < s2.length(); j++){
            rowSum[x] += tableVals[x][j];
        }
    }
    
    //print the rowSum
    cout << "The values in rowSum are: \n";
    for(int x = 0; x < s1.size(); x++){
        cout << rowSum[x];
    }
    
    //Calculate the colSum
   for(int x = 0; x < s2.length(); x++){
        for(int j = 0; j < s1.length(); j++){
            colSum[x] += tableVals[j][x];
        }
    }
   
    //print the colSum
    cout << "\nThe values in colSum is: \n";
    for(int x = 0; x < s2.size(); x++){
        cout << colSum[x];
    }
     
    //Get the start and end indexes
    for(int x = 0; x < s2.length(); x++){
        temp++;
        min++;
        if((colSum[x] >= 1)&&(colSum[x-1] == 0) && (temp > max) && (rowSum[x] > 0)){
            startIndex = x;
        }
        else if((rowSum[x] > 0) && (colSum[x] == 0) && (min > max)){
            max = min;
            startIndex = x-max;
            if(startIndex < 0){
                cout << max;
            }
            endIndex = x;
            temp = 0;
            min = 0;
        }
    }
    
    cout << "\nstartIndex = " << startIndex <<endl;
    cout << "endIndex = " << endIndex <<endl;
    
    //print out the longest substring
    cout << "\nThe longest substring between " << s1 << " and " << s2 << " is: ";
    for(int x = startIndex; x < s2.length(); x++){
        if(colSum[x] >= 1)
            cout << s2[x];
        else
            cout << " ";
    }
    cout << endl;
}

Open in new window


But... the thing is, this program doesn't work very well if there are same letters multiple times... like, if I pass in thisworks, and hellothisworks... my program prints out othisworks as the longest common substring...

This is the output generated by my code:

 
Enter the first string: thisworks
Enter the second string: hellothisworks
You have entered thisworks as your first string, and hellothisworks as your second string.
thisworks is 9 long.
hellothisworks is 14 long.
00000100000000
10000010000000
00000001000000
00000000100001
00000000010000
00001000001000
00000000000100
00000000000010
00000000100001
The values in rowSum are: 
121212112
The values in colSum is: 
100011112111122
startIndex = 4
endIndex = 1

The longest substring between thisworks and hellothisworks is: othisworks

Open in new window


Could anyone help me figure this out?

Thanks in advance!
0
Comment
Question by:errang
  • 16
  • 13
30 Comments
 

Author Comment

by:errang
ID: 35734720
Hm... I replaced this code segment

for(int x = 0; x < s2.length(); x++){
        temp++;
        min++;
        if((colSum[x] >= 1)&&(colSum[x-1] == 0) && (temp > max) && (rowSum[x] > 0)){
            startIndex = x;
        }
        else if((rowSum[x] > 0) && (colSum[x] == 0) && (min > max)){
            max = min;
            startIndex = x-max;
            if(startIndex < 0){
                cout << max;
            }
            endIndex = x;
            temp = 0;
            min = 0;
        }
    }

Open in new window


with

 
for(int x = 0; x < s1.size(); x++){
        for(int y = 0; y < s2.size(); y++){
            if(tableVals[x][y] == 1){
                tempx = x-1;
                tempy = y-1;
                if((tableVals[tempx][tempy] == 1) || (tableVals[tempx+2][tempy+2] == 1))
                    tableVals[x][y] = 1;
                else
                    tableVals[x][y] = 0;
            }
        }
    }

Open in new window



And there's a bit of an improvement... but it still doesn't work perfectly for all strings...
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35735237
Line 4: tempx = x-1;
If x is 0, then tempx is -1. But you are using tempx as an index into tableVals.

For example, you get tempx = -1 for input strings:  abab   and    baaba
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35735238
What pseudo-code are you basing this implemention? Do you have a link?
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:errang
ID: 35735269
>>What pseudo-code are you basing this implemention? Do you have a link?

not exactly... just something me and my friends came up with...

I actually fixed most of the problems with that code... but I still can't get it to work when i have multiple letters... like abbbbccccddddeeeeffff and cccccccddddddeeeeefffffaaaaa

Here's my new code:

#include <iostream>
using namespace std;

void makeTable(string, string);
void print(int tableVals[][], int out, int in);

int main (int argc, const char * argv[])
{

    string firstString;
    string secondString;
    
    cout << "Enter the first string: ";
    cin >> firstString;
    cout << "Enter the second string: ";
    cin >> secondString;
    
    cout << "You have entered " << firstString << " as your first string, and " << secondString << " as your second string." <<endl;
    
    cout << firstString << " is " << firstString.length() << " long." <<endl;
    cout << secondString << " is " << secondString.length() << " long." <<endl;
    
    
    if(firstString.length() < secondString.length())
        makeTable(firstString, secondString);
    else
        makeTable(secondString, firstString);
    return 0;
}

void makeTable(string s1, string s2){
    int tableVals[s1.length()][s2.length()];
    int rowSum[s1.length()];
    int colSum[s2.length()];
    int tempx = 0;
    int tempy = 0;
    int pasty = 0;
    
    //Initialize rowSum
    for(int x = 0; x < s1.length(); x++){
        rowSum[x] = 0;
    }
    
    //Initialize colSum
    for(int x = 0; x < s2.length(); x++){
        colSum[x] = 0;
    }
    
    //Build the table
    for(int i=0; i<s1.size(); i++){
        for(int j=0; j<s2.size(); j++){
            if(s1[i] == s2[j])
                tableVals[i][j] = 1;
            else
                tableVals[i][j] = 0;
        }
    }
    
    //Print the table
    for(int x = 0; x < s1.length() ; x++){
        for(int y = 0; y < s2.length() ; y++){
            cout << tableVals[x][y];
        }
        cout << endl;
    }
    
    //Calculate the rowSum
    for(int x = 0; x < s1.length(); x++){
        for(int j = 0; j < s2.length(); j++){
            rowSum[x] += tableVals[x][j];
        }
    }
    
    //print the rowSum
    cout << "The values in rowSum are: \n";
    for(int x = 0; x < s1.size(); x++){
        cout << rowSum[x];
    }
    
        
    for(int x = 0; x < s1.size(); x++){
        for(int y = 0; y < s2.size(); y++){
            if(tableVals[x][y] == 1){
                tempx = x-1;
                tempy = y-1;
                if((tableVals[x-1][y-1] == 1) || (tableVals[x+1][y+1] == 1))
                    tableVals[x][y] = 1;
                else
                    tableVals[x][y] = 0;
            }
        }
    }
    
    //Print the table
    cout << "\nThe new table is: " <<endl;
    for(int x = 0; x < s1.length() ; x++){
        for(int y = 0; y < s2.length() ; y++){
            cout << tableVals[x][y];
        }
        cout << endl;
    }

    
    //Calculate the colSum
    for(int x = 0; x < s2.length(); x++){
        for(int j = 0; j < s1.length(); j++){
            colSum[x] += tableVals[j][x];
        }
    }
    
    //print the colSum
    cout << "\nThe values in colSum is: \n";
    for(int x = 0; x < s2.size(); x++){
        cout << colSum[x];
    }

    //print out the longest substring
    cout << "\nThe longest substring between " << s1 << " and " << s2 << " is: ";
    for(int x = 0; x < s1.length(); x++){
        for(int y = 0; y < s2.length(); y++){
            if((tableVals[x][y] == 1) && ((tableVals[x+1][y+1] == 1) || tableVals[x-1][y-1] == 1)){
                cout << s2[y];
                pasty = y;
            }
        }
        if(tableVals[x+1][pasty+1] == 0){
            cout << endl;
        }
    }
}

Open in new window


Is there any good way to identify the longest sequence of diagonal 1's in a 2d array of 1's and 0's?

Here's an output for the same input with the first version:

 
Enter the first string: thisworks
Enter the second string: hellothisworks
You have entered thisworks as your first string, and hellothisworks as your second string.
thisworks is 9 long.
hellothisworks is 14 long.
00000100000000
10000010000000
00000001000000
00000000100001
00000000010000
00001000001000
00000000000100
00000000000010
00000000100001
The values in rowSum are: 
121212112
The new table is: 
00000100000000
10000010000000
00000001000000
00000000100000
00000000010000
00000000001000
00000000000100
00000000000010
00000000100001

The values in colSum is: 
10000111211111
The longest substring between thisworks and hellothisworks is: thhisworks

Open in new window


I'm about 90% sure my problems would be solved if this function got rid of the random 1's in the 2d array... but I can't figure out anything I missed with it...

for(int x = 0; x < s1.size(); x++){
        for(int y = 0; y < s2.size(); y++){
            if(tableVals[x][y] == 1){
                tempx = x-1;
                tempy = y-1;
                if((tableVals[x-1][y-1] == 1) || (tableVals[x+1][y+1] == 1))
                    tableVals[x][y] = 1;
                else
                    tableVals[x][y] = 0;
            }
        }
    }

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35735340
You have two sum variables that you compute but never use (other than printing them out).
You have tempx and tempy set, but not used.
Line 6: tableVals[x-1][y-1] == 1

If input is abab   and   baaba, then you reach this line with x = 0, y = 1; and then x-1 is -1 which you use as an index into tableVals.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35735357
Isn't this a homework assignment?

If so, then full solutions (even if they are wrong) should not be posted.
0
 

Author Comment

by:errang
ID: 35735532
>>Isn't this a homework assignment?

It was more of a discussion topic, my professor told us to think it over, and it was driving me crazy.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35735593
To make your program more portable, you can use vector:
void makeTable(string s1, string s2){ 
    vector< vector<int> > tableVals(  s1.size(),  vector<int>(s2.size())  );

Open in new window

>> it was driving me crazy
Yes, that is the purpose and fun part of these discussions.

I suggest you think carefully about why you have a -1 index. That certainly should raise a red flag. I'll be back tomorrow to see what thoughts you have on this.

When you have a recurrence in the top-level design (see below links), then you have to be careful after setting up initial values, that you continue the recurrence at the right index values.

I assume that you team started with some kind of pseudo-code. Perhaps this:
  http://en.wikipedia.org/wiki/Longest_common_substring_problem#Dynamic_programming

   http://www.ics.uci.edu/~dan/class/161/notes/6/Dynamic.html

I like to work with tiny problems first that I can work out manually just using the highest-level principles (rather than the more detailed pseudo-code that follows in these links). Once I figure out how to do it manually (paper and pencil; sometimes a deck of cards), then the pseudo-code can begin to make more sense.


0
 
LVL 32

Expert Comment

by:phoffric
ID: 35736604
From the above link is following top-level recursion:
Let Li, j = maximum length of common strings that end at A[ i ] & B[j].   Then,
        A[ i ] = B[j] ¿ Li, j = 1 + Li-1, j-1
        A[ i ] ¿ B[j] ¿ Li, j = 0

Make sure that you really understand this recursion. As simple looking as this seems, make sure that you can walk through a string having property that L4,7 = 2, and then consider both cases A[ i ] = B[j]  and   A[ i ] ¿ B[j]  in order to come up with L5,8.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35736634
Repeating to get the symbols right...

From the above link is following top-level recursion:
Let Li, j = maximum length of common strings that end at A[ i ] & B[j].   Then,
        A[ i ] == B[j]  -->  L i, j = 1  +  L i-1, j-1
        A[ i ] !=  B[j]  -->  L i, j = 0
Make sure that you really understand this recursion. As simple looking as this seems, make sure that you can walk through a string having property that L4,7 = 2, and then consider both cases A[ i ] == B[j]  and   A[ i ] != B[j]  in order to come up with L5,8.

If you post a short string having both these cases, then we'll certainly be on the same page.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35737617
I'll be back tonight. Two things..

If you want to use dynamic programming, then you have a recurrence relation for this problem. Somehow your team came up with the code, but what is the top-level principle that you are using which represents your point of view?

Also, you should check the program listing in http:#35735330 for  abab and baaba to see if it works; as well as for your strings:   abbbbccccddddeeeeffff and cccccccddddddeeeeefffffaaaaa. When I tried it for both these cases, the results were incorrect.

When I used the top-level recurrence in http:#35736634, the results for these two cases came out correct.
0
 

Author Comment

by:errang
ID: 35739777
Yeah, I understand that, I've asked for help on assignments before, but can I still give some points to TheKashyap? He obviously put some effort into his post.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35742598
If TheKashyap wishes to make posts that are helpful and continuing in line with the requirements of this thread, then TheKashyap can certainly do so (as well as any other experts who wish to help). Then you can share points to the extent that the posts help you with this question.

You mentioned that the top-level design approach given by your professor was to look at diagonals. This certainly makes sense. I am wondering whether your professor gave any more guidelines.

If you look at http:#35736634 the recurrence relation is very much diagonal oriented:
        A[ i ] == B[j]  -->  L i, j = 1  +  L i-1, j-1
since the coordinates (i,j) is diagonal to (i-1,j-1).

Recall that I said that if you can solve this problem using paper and pencil, then implementing it should be much easier. Here is an excellent video that shows step-by-step a diagonal paper and pencil approach for solving this problem.

Longest Common Substring (LCS) algorithm walk through
    http://www.youtube.com/watch?v=RUckZMzqUcw

BTW - I would not expect your professor to accept code that allows -1 for a standard array index. (I say standard because you can define arrays that have any index domain that you wish.) But, if this is just for practice without handing in the code, then that choice is up to you. After you get this to work, I encourage you to convert the problem to standard portable C++ code.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 2000 total points
ID: 35742613
Does the professor want you to be able to identify a Longest Common Substring, or all Longest Common Substrings (either the same at different starting positions or different substrings of same maximal length)?
0
 

Author Comment

by:errang
ID: 35743141
>>Does the professor want you to be able to identify a Longest Common Substring, or all Longest Common Substrings (either the same at different starting positions or different substrings of same maximal length)?

I'm just supposed to find a longest common string between two strings.
0
 

Author Comment

by:errang
ID: 35743167
>>Longest Common Substring (LCS) algorithm walk through
    http://www.youtube.com/watch?v=RUckZMzqUcw

That does seem simple, but the video didn't go over one thing, what happens to the set if I find a larger set than the current one? Like, what if after finding 'lol' i find that there's an 'ipop' in the other string... how would I know which letters to add to the set when all i know is the length of the longest set?
0
 

Author Comment

by:errang
ID: 35743252
Well, I coded up what was described in the video, it actually is very simple like you said:

void makeTable(string s1, string s2){
    int tableVals[s1.length()+1][s2.length()+1];
    int longest = 0;
    string longestCS = "";
    int tempx = 0;
    int tempy = 0;
    int pasty = 0;
    
    for(int i = 0; i<s1.size()+1; i++){
        for(int j = 0; j<s2.size()+1; j++){
            tableVals[i][j]=0;
        }
    }
    
    //Build the table
    for(int i=0; i<s1.size()+1; i++){
        for(int j=0; j<s2.size()+1; j++){
            if(s1[i] == s2[j]){
                tableVals[i+1][j+1] = tableVals[i][j] + 1;
                longestCS = longestCS + s2[j];
                longest++;
            }
        }
    }
    
    //Print the table
    for(int x = 0; x < s1.length() ; x++){
        for(int y = 0; y < s2.length() ; y++){
            cout << tableVals[x][y];
        }
        cout << endl;
    }
    
    cout << "The longest common string is: " << longestCS <<endl;
}

Open in new window


I'm gonna work on dealing with a second longest string... could you give me a hint as to how I'd keep track of those? Instinctively, I'd have a longest and secondLongest variable, and I would break the pattern, I would set secondLongest = longest, and then store the string the same way in another string... is that the way we should go about this?
0
 

Author Closing Comment

by:errang
ID: 35743495
Thanks for all the help! Finally got the problem, basically, I didn't build the string as I went along at run time, instead I used the value of longest, to backtrack through the table, and then I would build a reversed version of the longest string...

Then I just go through another loop and build a non-reversed version of it.

By the way... would it be possible to award 150 points to theKashyap? he did post a viable solution, taking the time to write it up.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35743531
You can RA for the moderator to open the question. However, when I ran his program, it failed for my example (abab and baaba) and one of your examples, so he would have to keep working with you in a way that helps you come up with a solution that you mutually agree upon.

Alternatively, if you ask the LCS question differently using his C++ class approach, then likely he will respond to guide you, and then you can give him all the points for that question.

As for this question, you asked a few questions since my last post. But I have the sense that you answered them all on your own. If not, let me know and I'll be happy to address them. I'll be back tomorrow to check; and also I'll review and test your latest version tomorrow and let you know if I find any problems.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35743954
>> Finally got the problem
Ok, good, since the last listing post didn't give the right answer. Also, in the video, the excel sheet had an extra row and column - not sure if you did that for your final program. (However, I think you could design an algorithm that does not need an explicit extra column and row and still stay within matrix boundaries.) Also, you can design an algorithm to have only two rows which can be a nice savings if m and n are both large.

>> I didn't build the string as I went along at run time, instead I used the value of longest, to backtrack through the table
Good, pseudo-code is just that - a schematic of intent. Building a string is time-consuming, especially when there are many false starts in the string building.

Recall from the videos of your previous LCSubstring question that a substring can be compressed into two integers (say, start offset and length; or say, length and cell number; or say, length and end offset - multiple ways to compress - I prefer the latter since there is less work in the inner loop).

After you have the table built, there should be no need to backtrack through the entire table if you have saved the max length with an offset.

You should be saving the current max length that corresponds to Excel cell H16 (i.e., "Longest Match so far"), so the only other thing you need to save when H16 changes is an integer offset (either first or last).
0
 

Author Comment

by:errang
ID: 35743965
>>Ok, good, since the last listing post didn't give the right answer. Also, in the video, the excel sheet had an extra row and column - not sure if you did that for your final program. (However, I think you could design an algorithm that does not need an explicit extra column and row and still stay within matrix boundaries.) Also, you can design an algorithm to have only two rows which can be a nice savings if m and n are both large.

yea, I created an extra row as stated in the video...

if you'd like to see my program, see if it has any flaws...=):

#include <iostream>
using namespace std;

void makeTable(string, string);

int main (int argc, const char * argv[])
{

    string firstString;
    string secondString;
    
    
    //Accept user input
    cout << "Enter the first string: ";
    cin >> firstString;
    cout << "Enter the second string: ";
    cin >> secondString;
    
    //Display user input
    cout << "You have entered " << firstString << " as your first string, and " << secondString << " as your second string." <<endl;
    
    //Display string lengths
    cout << firstString << " is " << firstString.length() << " long." <<endl;
    cout << secondString << " is " << secondString.length() << " long." <<endl;
    
    
    //Make sure that the longest string is passed as parameter #2 to the function.
    if(firstString.length() < secondString.length())
        makeTable(firstString, secondString);
    else
        makeTable(secondString, firstString);
    return 0;
}

//This is a fairly straightforward function that simply makes a table out of the two substrings to discover
//the longest possible substring.
void makeTable(string s1, string s2){
    int tableVals[s1.length()+1][s2.length()+1];
    int longest = 0;
    int secondLongest = 0;
    int startX = 0;
    int startY = 0;
    string longestCS = "";
    string properString = "";
    
    //Initialize the table with 0's everywhere.
    for(int i = 0; i<s1.size()+1; i++){
        for(int j = 0; j<s2.size()+1; j++){
            tableVals[i][j]=0;
        }
    }
    
    //Build the table
    for(int i=0; i<s1.size()+1; i++){
        for(int j=0; j<s2.size()+1; j++){
            if(s1[i] == s2[j]){
                tableVals[i+1][j+1] = tableVals[i][j] + 1;
                if(tableVals[i][j] == longest){
                    longest++;
                    startX = i;
                    startY = j;
                }
                if(tableVals[i][j] == secondLongest){
                    secondLongest++;
                }
                if(secondLongest > longest){
                    longest = secondLongest;
                }
            }
        }
    }
    
    //Go through the string and print out the relevant substring.
    for(int x = (startY-longest)+1; x <= startY; x++){
        properString = properString + s2[x];
    }

    //Print the table
    cout << "This is the table if you would like to examine the algorithm." <<endl;
    for(int x = 0; x < s1.length() ; x++){
        for(int y = 0; y < s2.length() ; y++){
            cout << tableVals[x][y];
        }
        cout << endl;
    }

    cout << "The longest common substring is: " << properString <<endl;
}

Open in new window


I tested it out with various random strings with multiple letters, as well as the example you provided in one of your posts... abab and baaba.
0
 
LVL 6

Expert Comment

by:theKashyap
ID: 35744401
I have therefore deleted three posts by theKashyap which were too precise in terms of a solution.
My apologies. I was under the impression that we are expected to provide as precise a solution as possible.
In any case my solution was way off the question as I realized after posting. :-)
It solved the problem in the subject, but didn't answer the question the OP was asking.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35749564
I reviewed your code in http:#35743965. After a few tests, I think it solves your problem. Congrats!
 Here are my comments:
Good that you got rid of the -1 array index!
Good that you saved a string index rather than build the string on the fly.
When you print the table (for debug), you should show the extra column and row.
You can design this to avoid the extra row and column.
Too much logic in your innermost loop will degrade performance; and there are two unneeded variables in this loop.
>> //Go through the string and print out the relevant substring.
You can (should) remove the loop and just use substr:
    http://www.cplusplus.com/reference/string/string/substr/
====
@theKashyap,
>> It solved the problem in the subject

I no longer have your code, but when I ran it, it didn't give the longest common substring of either:
   { abab , baaba }
or
  { abbbbccccddddeeeeffff , cccccccddddddeeeeefffffaaaaa }.
What do you get for these two cases?

>> I was under the impression that we are expected to provide as precise a solution as possible.
   For projects that are academic in nature, your posts should provide guidance, but you should allow the author to do the coding.
    http://www.experts-exchange.com/help.jsp?hi=21
0
 

Author Comment

by:errang
ID: 35749922
>>I reviewed your code in http:#35743965. After a few tests, I think it solves your problem. Congrats!

Sweet, thanks =)

>>You can design this to avoid the extra row and column.

Yea, I had startX in the loop because at one point, I was going back through the table to find the largest number, and then back track through the table... then I realized I didn't need to do that when I could just get the string that's at the top of the table.

>>When you print the table (for debug), you should show the extra column and row.

That bit of code was a left over from my initial attempt, and I just forgot to add 1 to the lengths of the strings.

>>Too much logic in your innermost loop will degrade performance; and there are two unneeded variables in this loop.

Hm... not sure how I can simplify here, and still keep the lengths of the two longest strings.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35751148
>> still keep the lengths of the two longest strings
Why do you need the 2nd longest string when you say you only are looking for the longest string?
0
 

Author Comment

by:errang
ID: 35751253
>>Why do you need the 2nd longest string when you say you only are looking for the longest string?

main reason, is that if I came across a new string that was longer than the current string... I would have no way to keep track of how long that new string is... or, if there was, I didn't see it at the time
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35751273
>>  if I came across a new string that was longer than the current string... I would have no way to keep track of how long that new string is

Let's see if an analogy helps. In this problem you are trying to find the largest something (in this case a Common Substring).

If you had to write a function that iterated through an array of integers in order to find the largest number and the position in the array, would you have to keep track of the 2nd largest number and the 2nd position of the 2nd largest number, in addition to tracking the largest number and the position of the largest number?
0
 

Author Comment

by:errang
ID: 35751290
no... I guess not, but I was running into some errors where it would keep repeating letters, the current if else statements fixed that.

after that, it stopped looking at new strings... I guess I could try experimenting with it a bit more.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35751294
Think about the video.. Were there two longest cells - one for current longest and one for 2nd longest?
0
 

Author Comment

by:errang
ID: 35751327
hm... ok, lemme see
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month15 days, 14 hours left to enroll

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question