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.

Quote:

---

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)
}

---