# finding longest common string by recursion

Page 1 of 1

## 10 Replies - 7188 Views - Last Post: 09 September 2009 - 08:33 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=81506&amp;s=fe047570e715ede045d14f333e3efd21&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 drordh

Reputation: 0
• 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;

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

• Expert Schmexpert...

Reputation: 235
• 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?

### #3 drordh

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

## Re: finding longest common string by recursion

Posted 18 January 2009 - 09:07 AM

Gloin, 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

### #4 Pwn

• D.I.C Regular

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

## Re: finding longest common string by recursion

Posted 18 January 2009 - 09:21 AM

drordh, 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.

### #5 drordh

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

## Re: finding longest common string by recursion

Posted 18 January 2009 - 10:07 AM

Pwn, on 18 Jan, 2009 - 08:21 AM, said:

drordh, 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
thats why if i have AABBB and BBBAA==>BBB
just BBB

### #6 Pwn

• D.I.C Regular

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

## Re: finding longest common string by recursion

Posted 18 January 2009 - 10:43 AM

drordh, 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.

### #7 drordh

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

## Re: finding longest common string by recursion

Posted 18 January 2009 - 11:45 AM

Pwn, on 18 Jan, 2009 - 09:43 AM, said:

drordh, 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...

### #8 drordh

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

## Re: finding longest common string by recursion

Posted 19 January 2009 - 10:08 AM

drordh, on 18 Jan, 2009 - 10:45 AM, said:

Pwn, on 18 Jan, 2009 - 09:43 AM, said:

drordh, 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!

### #9 weml0169

Reputation: 0
• 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:)

### #10 NickDMax

Reputation: 2255
• 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.

Thanks.

Plus -- don't hijack other people's threads -- if you want help with this please start a new topic.

### #11 viveks89

Reputation: 1
• 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???