[chghrtfzzy]

Hi. I'm totally new to programming and these boards, and I'm having a lot of trouble with this project.
I am supposed to write a C++ program that finds the longest common substring of two entered words. The program repeatedly prompts the user for two words and prints the longest substring that the two words have in common to the screen. The program quits when the user closes the input stream. I know we use for loops and nested loops . . . but that's all I know I still don't quite get the "for loop" thing. Can someone explain that? The prof also said something about closing the program after the user enters cntrl+z twice? How do I do that? I'm not sure what that means.

Please help. I'm so lost
Thanks for any help.

This post has been edited by chghrtfzzy: 05 July 2008 - 11:31 PM

[lordms12]

This is a famous problem and can be solved using dynamic programming algorithm, just Google and you will find a lot of good materials.

This post has been edited by lordms12: 06 July 2008 - 11:40 AM

[NickDMax]

a "for loop" is a rather simple construct that is most often used to execute loops with a known number of iterations -- i.e. a loop that counts its way though a series of numbers (though this is by no means the only use if the for loop).

int x; // a counter variable
std::cout << "I can count to ten." << std::endl;
for (x=0; x <10; x++) {
	std::cout << x << ", ";
}
std::cout << "\nDone!\nNow Gimme Some CANDY!" << std::endl;

The loop has four parts:

for(initialization; condition needed to continue; increment) {
..inside of loop...
}

in the 'initialization' part you set things up, like set your loop variable to 0.

in the 'condition needed to continue' you set the condition needed for the inner portion of the loop to execute -- x < 10

in the increment step you modify the control variable. x++

[chghrtfzzy]

lordms12, on 6 Jul, 2008 - 11:39 AM, said:

This is a famous problem and can be solved using dynamic programming algorithm, just Google and you will find a lot of good materials.

Hi.
I've Googled it. The search comes with a lot of "longest common subsequence" results. I'm not sure what a subsequence but I think I've read somewhere that it isn't the same thing as a substring? And the other results used some stuff like Python (?) and C# (?), etc So far we've only covered iostream, string, int, for loops, while loops, if-else statements, and do-while loops. We're only supposed to use those.

NickDMax, on 6 Jul, 2008 - 11:53 AM, said:

a "for loop" is a rather simple construct that is most often used to execute loops with a known number of iterations -- i.e. a loop that counts its way though a series of numbers (though this is by no means the only use if the for loop).

int x; // a counter variable
std::cout << "I can count to ten." << std::endl;
for (x=0; x <10; x++) {
	std::cout << x << ", ";
}
std::cout << "\nDone!\nNow Gimme Some CANDY!" << std::endl;

The loop has four parts:

for(initialization; condition needed to continue; increment) {
..inside of loop...
}

in the 'initialization' part you set things up, like set your loop variable to 0.

in the 'condition needed to continue' you set the condition needed for the inner portion of the loop to execute -- x < 10

in the increment step you modify the control variable. x++

Thank you So its just a counting thing? So can it be used to compare strings-- letter by letter?

This post has been edited by chghrtfzzy: 06 July 2008 - 02:36 PM

[NickDMax]

Well yes... mostly you want to put logic like that into the inside of the loop (though often you will see some programmers pack all kinds of crap into the other three section -- I believe that you program could be done in such a way, but I don't recommend it).

There are may ways to find the longest substring of a string. You should probably start with something simple and work your way into more and more sophisticated methods.

IT helps to start by trying to do this yourself. Write out two words and try to think of a step by step way to find common substrings.

so given Antidisestablishmentarianism and establishment.

Think of all the ways that you can find common substrings. Once you work out a method -- try to formalize it into an algorithm. THEN try to code it.

[chghrtfzzy]

A friend told me that while loops would be more useful in this case since for loops aren't conventional . . . is this true?

[brainy_creature]

i tried coding this problem but am unable to!
can any body guide me how to go about it?? its a really nice question

[captainhampton]

The best way to understand the for loop, or loops in general is to see how each can be interchanged to make inheretenly the same type of loop. How is your understanding on while loops, do while loops, etc.

[brainy_creature]

am ok with loops i think
i just dont get the concept of this problem
i put two strings in two arrays then i thought i can compare the first position of the array1 with all the characters of array 2
if it matches then i thought i would move on to the next charcter of array1 and would like to continue from that position of array2

i tried coding but its getting really complicated!! i dont think am making sense
pls advice so that i can try again

[chghrtfzzy]

#include <iostream>
#include <string>

using namespace std;
int main () {
	
	string first, second, lcsub, max;
	
	cout << "Enter two words" << endl;
	cin >> first >> second;
		for (int i=0; i < first.length(); i++)
			for (int j=0; j < second.length(); j++)
				for (int k=1; k <= first.length() && k <= second.length(); k++){
					if (first.substr(i,k) == second.substr(j,k)){
						lcsub = first.substr(i,k);
					}
					else{
						if (lcsub.length() > max.length())
							max=lcsub;
						lcsub="";
					}
				}
					if (lcsub.length() > max.length())
							max=lcsub;
						lcsub="";
						cout << "Longest Common Substring: " << max << endl;
	return 0;
}

Okay, so I got the longest common substring . . . now I just need to figure out how to repeatedly prompt the user to enter two words and close the input stream using ctrl+z

This post has been edited by chghrtfzzy: 08 July 2008 - 03:02 PM

[chghrtfzzy]

Got it! Still doesn't recognize capitalized letters (but that wasn't part of the requirements)

#include <iostream>
#include <string>

using namespace std;
int main () {
	
	while(1) {
		
		string first, second, lcsub, max;
		
		cout << "Enter two words" << endl;
		cin >> first >> second;
		if(cin.eof()) {
			return 0;
		}
		for (int i=0; i < first.length(); i++){
				for (int j=0; j < second.length(); j++){
					for (int k=1; k <= first.length() && k <= second.length(); k++){
						if (first.substr(i,k) == second.substr(j,k)){
							lcsub = first.substr(i,k);
						}
						else{
							if (lcsub.length() > max.length())
								max=lcsub;
							lcsub="";
						}
					}
						if (lcsub.length() > max.length())
								max=lcsub;
						lcsub="";
				}
		}
		cout << "Longest Common Substring: " << max << endl << endl;
	}
	return 0;
}

[from_ashes]

since u r a starter i suggest u to follow the naive algorithm which is based on brute force...and after going clean with that u can follow dp(dynamic programming ) for optimized results.

[JackOfAllTrades]

Don't go dredging up 4 year old topics, please.