Multiple Longest Common Substring?

[iwantricexd]

Hi all,

I don't understand how to approach an overlap assignment (basically longest common substring?). The program will have a set of three strings(keys). I'm not supposed to compare the keys directly to each other. Instead, after you get the keys, input a sequence of N strings and compare the keys to these strings(for each key). I have to track the string that provides the greatest overlap and the size of the overlap; ties going to the first occurring word. We need to use an input file instead of taking input through the keyboard (input redirection refresher). We should use an input statement inside our conditional expression of a loop to keep acquiring input until the end of input file is reached. i.e.

while (cin >> stringName)
{
    //loop body code
}

other requirements: output: key, match ("No Match" when no overlap), and
overlap size for each key. Case and punctuation do matter.

Input file:

lud
mall
war
This list of words includes many facets of the 
problem but may not test all. Armed with your wit 
and a tool for development, you should create 
multiple possible scenarios to test whether your 
program hits the ball out of the park and executes 
correctly.

Example run using above input file:

Key: lud
Match: tool
Overlap: 1

Key: mall
Match: all.
Overlap: 3

Key: war
Match: No Match
Overlap: 0

I am supposed to use string functions .size () and .substr (). I know we need to use functions and (nested) loops to do this. I understand how to use these but don't really understand how to implement them for this problem. I'm having trouble write pseudo code. I've searched for longest common substring problems but that seems to only compare 2 strings, how would I compare each key to multiple strings and find the longest one? Can someone help me out with pseudo code and/or an algorithm to help me understand how to tackle this problem?

any and all help will be appreciated, thanks :)

[iwantricexd]

I'm mainly stuck on how to implement this for 3 different keys as opposed to just one.

[codingboss123]

can we see the code you have so far? does your code correctly find the overlaps just for the first keyword? if you can code if for the first keyword its not hard to make it work for the other two key words.

[iwantricexd]

#include <iostream>
#include <string>

using namespace std;

int longestOverlapSize (string str1, string str2) 
{
    int i = 0;
    int j = 0;
    int k = 1;
    string overlap, maxOverlap;
    int overlapSize = 0;
    
    
    for (i = 0; i < str1.size(); i++) 
    {
        for (j = 0; j < str2.size(); j++) 
		{	
			for (k = 1; k <= str1.size() && k <= str2.size(); k++)
			{
				if (str1.substr(i,k) == str2.substr(j,k))
				{
					overlap = str1.substr(i,k);
				}
				else
				{
					if (overlap.size() > maxOverlap.size())
						maxOverlap=overlap;
					overlap.clear();
				}
			}
				if (overlap.size() > maxOverlap.size())
						maxOverlap = overlap;
					overlap.clear();
		}
    }
	overlapSize = maxOverlap.size ();
	
	return overlapSize;
}

int main ()
{
    string one;
    string two;
    int overlap;
    
    
    cout << "Enter two strings to test for overlap: ";
    cin >> one >> two;
    
    overlap = longestOverlapSize (one, two); 
    
    cout << "overlap: " << overlap << endl;
    
    return 0;
    
    
}

This isn't the whole assignment, but trying to take things one at a time. The function I have now returns overlap fine, but there's two problems. The assignment specification indicates that case does matter, and any overlaps have to be at the beginning or end of the word. The function I have now isn't case sensitive and will tell me I have 1 overlap when I inputted "how" and "dog" (it includes matches from the middle of the word as well). How could I modify this to be case sensitive and only start at the beginning or end?