10 Replies - 5669 Views - Last Post: 09 September 2009 - 08:33 AM Rate Topic: -----

#1 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

finding longest common string by recursion

Posted 18 January 2009 - 08:20 AM

hey!
i wrote a programme that find the longest common string.
but its not good for all cases..
its good if: first string is {bbbaa} second {aabbb}==>bbb
and its not good if : first is {aabbb} second {bbbaa}==>aa
its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD
its good for {hibdrorhab} {abddrorhib}==>bdrorhb

what sould i fix?


#include <iostream.h>
# include <stdio.h>
# include <string.h>

#define MAX 100  

void comp(char st1[], char st2[], char temp[], char biggest[], 
		 int x, int y, int i, int n, int j);

void help(char temp[],char biggest[]);

/*programme that find the common longest string among 2 strings
looking at first for the longest at str1 and after at str2
each time i check the longest common string from the next char

x=counter of st1,
y=counter of st2,
i=counter of temp string, 
n=counter where the last place that find identity,
j=care that after each string that i find will add 1 to the counter till its =strlen(st1) 
*/
void main()
{
	int i=0;
	
	char st1[MAX] = {"aabbb"}, st2[MAX] ={"bbbaa"};
		 
	char temp[MAX] = {0},big1[MAX] = {0}, big2[MAX] = {0};
	
/*	cout<<"Please enter the first string:";
	cin>>st1;
	
	cout<<"Please enter the second string:";
	cin>>st2;
  */  
	comp(st1, st2, temp, big1, 0, 0, 0, 0, 1);//calling to recursive num1
	
	comp(st2, st1, temp, big2, 0, 0, 0, 0, 1);//calling to recursive num2
	
	cout<<"The longest common string is:";
	
	//if ((strlen(big1)) > (strlen(big2)))//printing order to the longest string
		for(i=0;i<=strlen(big1);i++)
			cout<<big1[i];
		cout<<endl;
	//else
		for(i=0;i<=strlen(big2);i++)
			cout<<big2[i];
		
		cout<<endl;
}



void comp(char st1[], char st2[], char temp[], char biggest[], 
		 int x, int y, int i, int n, int j)//checking the strings
{
	if (st1[x]!= st2[y])//if not equal
	{
		
		if (y!=strlen(st2))//checking if it is not the last char
		{
			comp (st1,st2,temp,biggest,x,y+1,i,n,j);//moving the pointer of 
			return;												//the second str			
		}
		if (x!=strlen(st1))//checking if it is not the last char
		{
			comp (st1,st2,temp,biggest,x+1,n,i,n,j);//moving the pointer 
			return;												//of the second str
		}
		
	}
	else //if equal
	{
	  temp[i]=st1[x];//put the common string in temp 
		if ((st1[x+1]!=NULL) && (st2[y+1]!= NULL))//checking if it is not the last char
		{
			comp (st1,st2,temp,biggest,x+1,y+1,i+1,y+1,j);//moving the pointer 
			return;													//	of both str
		}  
	}
	help(temp,biggest);

	if (st1[j]!=NULL)//checking if it is not the last char  
		comp (st1,st2,temp,biggest,j,0,0,0,j+1);//doing a new search from the next place
	
}



void help(char temp[],char biggest[])//function that check which 
{									//string is bigger and initial the second
	int i=0;

	if ((strlen(temp))>(strlen(biggest)))//checking if big and then copy
		strcpy(biggest, temp);
	while(i <= MAX)//initial temp after copy
	{
		temp[i]=NULL;
		i++;		
	}
}

This post has been edited by drordh: 18 January 2009 - 09:05 AM


Is This A Good Question/Topic? 0
  • +

Replies To: finding longest common string by recursion

#2 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: finding longest common string by recursion

Posted 18 January 2009 - 08:41 AM

First of all, fix code tags around your code so it gets readable.. [ code] code here [ /code] (without blanks)
Second, this is a rather complicated problem so don't expect an immediate answer.

Third,

Quote

its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD
its good for {hibdrorhab} {abddrorhib}==>bdrorhb


This is different from Longest common substring where intermediate characters are disallowed?
Was This Post Helpful? 0
  • +
  • -

#3 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding longest common string by recursion

Posted 18 January 2009 - 09:07 AM

View PostGloin, on 18 Jan, 2009 - 07:41 AM, said:

First of all, fix code tags around your code so it gets readable.. [ code] code here [ /code] (without blanks)
Second, this is a rather complicated problem so don't expect an immediate answer.

Third,

Quote

its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD
its good for {hibdrorhab} {abddrorhib}==>bdrorhb


This is different from Longest common substring where intermediate characters are disallowed?


hey!
thanks!
i didnt see that it was like this..
second: intermediate characters are allowed.
and that make it problem
:)
Was This Post Helpful? 0
  • +
  • -

#4 Pwn  Icon User is offline

  • D.I.C Regular

Reputation: 19
  • View blog
  • Posts: 458
  • Joined: 25-November 07

Re: finding longest common string by recursion

Posted 18 January 2009 - 09:21 AM

View Postdrordh, on 18 Jan, 2009 - 08:07 AM, said:

second: intermediate characters are allowed.
and that make it problem
:)


if intermediate chars are allowed, then the first example, aaabb and bbaaa should return the entire string, since they both contain aaabb. if ABCD will match BADC then ababa should match aaabb because it's the same chars just different order. You need to nail down the rules before attempting to code; it will help keep your program in focus.
Was This Post Helpful? 0
  • +
  • -

#5 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding longest common string by recursion

Posted 18 January 2009 - 10:07 AM

View PostPwn, on 18 Jan, 2009 - 08:21 AM, said:

View Postdrordh, on 18 Jan, 2009 - 08:07 AM, said:

second: intermediate characters are allowed.
and that make it problem
:)


if intermediate chars are allowed, then the first example, aaabb and bbaaa should return the entire string, since they both contain aaabb. if ABCD will match BADC then ababa should match aaabb because it's the same chars just different order. You need to nail down the rules before attempting to code; it will help keep your program in focus.


no, so you didnt understand me well..
if i have ABCD and BACD i have to get ==>ACD
HILADKDK and HILAKD ==>HILAKD
thats why if i have AABBB and BBBAA==>BBB
just BBB
Was This Post Helpful? 0
  • +
  • -

#6 Pwn  Icon User is offline

  • D.I.C Regular

Reputation: 19
  • View blog
  • Posts: 458
  • Joined: 25-November 07

Re: finding longest common string by recursion

Posted 18 January 2009 - 10:43 AM

View Postdrordh, on 18 Jan, 2009 - 07:20 AM, said:

its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD


I think I understood this statement just fine. The two sets returns ABCD and that's the result you said you expected.
Was This Post Helpful? 0
  • +
  • -

#7 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding longest common string by recursion

Posted 18 January 2009 - 11:45 AM

View PostPwn, on 18 Jan, 2009 - 09:43 AM, said:

View Postdrordh, on 18 Jan, 2009 - 07:20 AM, said:

its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD


I think I understood this statement just fine. The two sets returns ABCD and that's the result you said you expected.


yes!
you understood... :)
Was This Post Helpful? 0
  • +
  • -

#8 drordh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 15-January 09

Re: finding longest common string by recursion

Posted 19 January 2009 - 10:08 AM

View Postdrordh, on 18 Jan, 2009 - 10:45 AM, said:

View PostPwn, on 18 Jan, 2009 - 09:43 AM, said:

View Postdrordh, on 18 Jan, 2009 - 07:20 AM, said:

its good for {AzB34CUDWQ} {DABC7ffD1}==>ABCD


I think I understood this statement just fine. The two sets returns ABCD and that's the result you said you expected.


yes!
you understood... :)



i succeed!!!
i had problem with my help function...
i erased the initial their and its work now!
because it couldnt save the string. i always erase it. :)
thank u anyway!
Was This Post Helpful? 0
  • +
  • -

#9 weml0169  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 09-September 09

Re: finding longest common string by recursion

Posted 09 September 2009 - 07:41 AM

hi:
where can i get the c or c++ source code of "longest common substring" using "gereralize suffix tree"?
thanks:)

Was This Post Helpful? 0
  • +
  • -

#10 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: finding longest common string by recursion

Posted 09 September 2009 - 08:14 AM

Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.

Post your code like this: :code:

Thanks.

Plus -- don't hijack other people's threads -- if you want help with this please start a new topic.
Was This Post Helpful? 0
  • +
  • -

#11 viveks89  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 06-January 09

Re: finding longest common string by recursion

Posted 09 September 2009 - 08:33 AM

Is it true that
we have to check for largest no of continuos letters in string 2 which are presnt in string1
It should be continuous in string2 but not in string1 right???
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1