Click here to Skip to main content
15,885,896 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
hi
C++
#include "stdafx.h"
#include "iostream"
#include <stdlib.h>
#include <string.h>
using namespace std; 
#define SIZE 100

void reset(char temp[]) //clears the array
{
for (int i=0;i <= strlen(temp);i++)
temp[i] = 0;
}

void lcs(char str1[], char str2[], char temp[], int x, int y, int i)
{
if (str1[x]==0)//end of string exit
return;
else
{
if (str1[x]==str2[y])//finds similar cells
{
temp[i]=str1[x];//copy to temp
if ((str1[x+1]!=0) && (str2[y+1]!=0))//checks that this is not the end of the strings and send 
return lcs (str1, str2, temp,x+1 ,y+1 , i+1);//the next cell to compare
}
else//the x&y are not the same
if (str2[y] == 0)//if the program finished going on the second string it reset the counter using 
return lcs (str1, str2, temp,x+1 ,strlen(temp), i+1);//temp and return the next cell from str1
if (str2[y+1] != 0)//compare x from str1 to y+1 from str2
return lcs (str1, str2, temp, x, y + 1, i);
if (str1[x] == 0)//compare x+1 from str1 to y from str2
return lcs (str1, str2, temp, strlen(temp), y, i);
}
}
void main()
{
char str1[SIZE]={0},str2[SIZE]={0},temp[SIZE]={0}, big[SIZE] = {0};//, biggest2[SIZE] = {0};
cout<<"Please enter the first string:";
cin>>str1;
cout<<"Please enter the second string:";
cin>>str2;
lcs(str1, str2, temp, 0, 0, 0);
for(int i=0;i<SIZE;i++)
	big[i]=temp[i];
reset(temp);
lcs(str2, str1, temp, 0, 0, 0);
cout<<"The longest common string is:";
if ((strlen(big)) > (strlen(temp)))
cout<<big<<endl;
else
cout<<temp;
}


Above code returns a, but when the inputs are:
Hgaksc
Agsmcdf

it should return gsc.

Please help me.
I can't find it's problem
Thanks
Posted
Updated 13-May-15 22:26pm
v2
Comments
CHill60 14-May-15 4:22am    
"gsc" is not a substring of either of those inputs

gsc is longest common sub sequence (not sub-sting).
Decription and Algorithm.
Algorithm implementation in C++ and several other languages.

But if you are looking for longest common sub-string then a is one of the correct answer.
 
Share this answer
 
Comments
CPallini 15-May-15 2:47am    
5.
Ashish Tyagi 40 15-May-15 3:28am    
Thanks :-)
As CHill60 says, it shouldn't return "gsc" at all - gsc isn't a substring of either input.
The LCS of those two inputs is a single character: either "g", "s", or "c" (and possibly "A" if you accept case independence)

A Common Substring is a short string of characters which appears in all the inputs, not a sequence of characters which appear in the same order without considering any extra characters between them.

I'd suggest you need to change your algorithm considerable if you want "gsc" returned - and learn to use the debugger to work out what is goign on while your code is running; you are going to need it! :laugh:
 
Share this answer
 
hi,
you named it as "longest common substring"
but your program is just returning the common alphabets of both the strings. Did not debug your code but a quick look suggests that this code correctly returns the common alphabets.
I think your intention is to use dynamic programming. Look at the implementation on this page[^].

If your intent is to find the common substring then another way(data structure) to check for sub string (of any length) is to implement a suffix tree.
Here[^] is a very helpful article regarding this approach.

Also as the Griff has suggested, you need to learn how to use your debugger. Its your best friend after google :)

hope this helps !!
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900