Thread: Maximum shared string

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    59

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

  2. #2
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    Any ideas?

  3. #3
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912

  5. #5
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    Sorry, I thought waiting 24 hours and then posting again was alright. Consindering it was on the second page. Bye.

  6. #6
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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)
    }
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 04-25-2008, 02:45 PM
  2. We Got _DEBUG Errors
    By Tonto in forum Windows Programming
    Replies: 5
    Last Post: 12-22-2006, 05:45 PM
  3. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 11:06 PM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM