Maximum shared string

Okay, I'm so close to getting this done but I've seem to hit a snag.
This program takes two strings and compares them and see what substrings both of them contain. I think it's better if I show it..

for example:

Enter Two strings.

zan
can

z is index 0, a is index 1 and n is index 2

Code:

INDEX   LENGTH   MSS
0            0        
1            2   an
2            1   a

Onto the problem with mine, right now it will only output when the substrings don't match. I'm hoping someone can point out to me a stupid error I made, I would appreciate it. Also I have traced the program and it works so that's why I'm here. Anyway here's my code:

Code:

/* 
	1. Maximum Shared Substring
	Description: A program that finds the MSS for two strings that are at most 1000 characters long.
	File: main.cxx
	Programmer: ****
	E-mail: ***
	Compiler: g++
	Last modified: 4/3/05
*/
using namespace std;
#include <iostream>
#include <string>
#include <iomanip>

void MMS(string strOne, string strTwo, int i);
void outputINDEX(int i);
void outputLENGTH(int subStringLength);
void outputMSS(string subString);

int main()
{
	string strOne, // Used to input first string
		   strTwo; // Used to input second string
	
	cout << "Enter two strings." << endl << endl;
	cin >> strOne >> strTwo;	
	cout << "INDEX" << setw(9) << "LENGTH" << setw(6) << "MSS" << endl << endl;
	return 0;
}

void MMS(string strOne, string strTwo, int i)
{
	char strOneLett; // Used to store the letter for testing
	int strTwoAns, // Used to store if a letter from string one is in string two
		subStringLength = 0, // Used to store length of the subString
		strOneLength = strOne.length() - 1, //Used to store length of stringOne - 1
		x = 0, // Used as loop variable for the second while loop
		i = 0; // Used as loop variable for the first while loop
	string subString = "";
	
	while(i <= strOneLength)
	{
		strOneLett = strOne.at(i);
		strTwoAns = strTwo.find(strOneLett);
		// When the letter is not found in string 2 it will output a blank row
		if(strTwoAns == -1)
		{
			outputINDEX(i);
			outputLENGTH("0");
			cout << endl;
		}
		// When the letter is found in string 2 it will see if it's only a shared charaacter or a substring
		if(strTwoAns != -1)
		{
			subString = "";
			while(x <= strOneLength)
			{
				subString = subString + strOne.at(x) ;
				strTwoAns = strTwo.find(subString);
				
				if(strTwoAns != -1 && x != strOneLength)
				{
				
				}	
				if(strTwoAns == -1)
				{
					subString  = subString - strOne.at(x); 
					subStringLength = subString.length();	
					outputINDEX(x);
					outputLENGTH(subStringLength);
					outputMSS(subString);
				}
				if(strTwoAns != -1 && x == strOneLength)
				{
					subStringLength = subString.length();
					outputINDEX(i);
					outputLENGTH(subStringLength);
					outputMSS(subString);	
					
				}
				x++;
			}
		}
		i++;
	}
}

// Output Functions
void outputINDEX(int i)
{
	
	cout << setw(5) << setiosflags(ios::right) << i;
}

void outputLENGTH(int subStringLength)
{
	cout << setw(9) << setiosflags(ios::right) << subStringLength;
}

void outputMSS(string subString)
{
	int width = subString.length() + 3;
	cout << setw(width) << setiosflags(ios::left) << subString << endl;
}

Any ideas?

I realized I was comping the wrong file all day so that code above doesn't even work. Anyone have any suggestions? I know how to find characters and strings but my problem is implementing it. I somehow have to take the first letter if string one and see if it's in string 2. Then I have to see if the second letter from string one is located next to the same character in string 2. If it is then I have to check to see if the next char does too. If not only output the Maximum shared string..

Like this:
String 1 is canz
string 2 is cans

This is how it should output
can
an
n

z and s aren't in either string so they don't get outputted.

Stop bumping the thread.

http://cboard.cprogramming.com/annou...ouncementid=51

Sorry, I thought waiting 24 hours and then posting again was alright. Consindering it was on the second page. Bye.

Originally Posted by StarOrbs

String 1 is canz
string 2 is cans

This is how it should output
can
an
n

I assume that it would also output c and a, since they are present in both strings.

This can be implemented fairly quickly using the STL sets. A set is a container that only allows one object for each value. For instance, you cannot have two 1's in a set. If you told a set to insert {1,3,5,7,3,4,7,8}, the contents would be {1,3,5,7,8} (although not necessarily ordered). Therefore, if you insert every substring of the string into the set, it will contain one of each substring.

After building both substring sets, you can use the set_intersection algorithm to find the substrings that are common to both sets.

Pseudocode:

Code:

Build substring set(string word)
{
For every possible length in the word
   for every possible offset in the word
      insert the substring of the word defined by offset,length
return substring set
}

main
{
Let A = Build substring set("cans")
Let B = Build substring set("canz")
output set_intersection(A,B)
}