10405 - Longest Common Subsequence

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Aug 06, 2007 5:29 pm

andysoft wrote:Can you please make a hint for me to feel the difference between bottom up and top down in this problem. o(n^2) solution of this kind:

Code: Select all

for i in sequence 1
  for j in sequence 2
    if s1[i]=s2[j] then
      ans[i][j] = ans[i-1][j-1] + 1; 
    else if .... and so on ...
is top-down? or bottom-up? :oops:
thanx in advance :)
BOTTOM UP :D

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Mon Aug 06, 2007 6:09 pm

oh, shame on me :D
then... it is the faster one, right?
would you mind if I write you some stuff on e-mail? it is too confidential for the forum :)
Now I lay me down to sleep...
my profile

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Aug 06, 2007 6:18 pm

andysoft wrote:oh, shame on me :D
then... it is the faster one, right?
would you mind if I write you some stuff on e-mail? it is too confidential for the forum :)
okay I dont mind.. email me at any time..
use this subject: 10405

mccarre
New poster
Posts: 5
Joined: Mon Oct 01, 2007 7:46 pm

10405 - i need a worst case input.

Post by mccarre » Sun Nov 04, 2007 6:45 am

I'm not doing it with DP yet. I'm almost positive my method works, and want to see it fail, before resorting to taking the DP approach.
I've tried mixing the strings so that the largest subsequences can be mixed in a random order, and i've tried tripling that approach, and I've tried adding random throw off characters, but I can't break my program. However it gets WA.

Here are 2 inputs I've used, first being the shortest complex string I could think of, and the second being the same with a lot of random characters in between:

Code: Select all

abcdxzyacdxzyb
acdxzybabcdxzy
a436432b5c346d23x6z56y54a62c6dx64665426z2y6b26
uaiopciudopxipzioypoibpuaobpcioodpiuxpozpy
Here's my code:

Code: Select all

#include <iostream>
#include <string>
#include <vector>

using namespace std;		//status: completed, again they giving fucking terrible input, so obviously I can't get it accepted.

string s1, s2;				//flip it around and compare it again? Tyr this and evaluate!
int maxsub; 	//also wiki longest common subsequence.
int s2iter; int s1iter;

void countinstuff()
{
	int max=1000000000, dist=0,temp,s2loc; bool foundone;

	/*find next occurance of a letter*/
	int i;
	for(i=0; i<s1.length(); i++)
		if(s2iter=s2.find(s1[i])+1) //this means it doesn't find anything... better then ==string::npos
			break;
	
	//cout << "Found first match at " << i<<", "<<(s2iter-1)<<endl;
	/***/

	for(int k=i; k<s1.length(); k++)
	{
			int bleh=k;
			foundone=false;
			max=1000000000;
			//cout << "k now equals " << k << endl;
			for(int j=k; j<s1.length(); j++)
			{
				/*find next occurance of a letter*/
				for(i=j; i<s1.length(); i++)
					if(temp=s2.find(s1[i],s2iter)+1) //this means it doesn't find anything... better then ==string::npos
						break;
				//cout << "Found a match at " << i<<", "<<(temp-1)<<endl;
				j=i;
				if(j==s1.length() && !foundone)	k=s1.length();
				else			foundone=true;
				/***/
				//cerr << "max = " << max << " & last dist = " << dist << endl;
				if(j!=s1.length())
				{	if((dist=(j-bleh)+(temp-s2iter))<max)
					{
						//cerr << "found better match at " <<j<<", "<<temp-1<<"while respectivly, k and s2iter are: "<<k<<", "<<s2iter<<endl;
						max=dist;
						s2loc=temp;
						k=j;
					}}
			}
			s2iter=s2loc;
			//cout << "Found best match at " << k<<", "<<(s2iter-1)<<endl;
			if(foundone)	maxsub++;
			//cout << "maxsub now equals " << maxsub << endl;
	}
	//cout << "**************************"<<endl;
}

int main()
{
while(cin >> s1)
{
	cin >> s2;

	s2iter=0;
	maxsub=1;
	//cout << "s1=" << s1 << " s2=" << s2<<endl;
	countinstuff();
	//cout << "maxsub=" << maxsub << " (before swap)"<<endl;

	cout << maxsub << endl;
}
return 0;
}
All i need is a complex input to break my code. Preferably not too long, so it isn't too hard to trace ^^.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue Nov 06, 2007 10:11 am

Please, use the existing thread.
As for the problem, you should read strings with fgets() (there can be blanks)

User avatar
vkubushyn
New poster
Posts: 6
Joined: Fri Oct 26, 2007 11:34 pm
Location: Las Vegas, NV

Help pls

Post by vkubushyn » Wed Dec 05, 2007 8:52 am

Hi I also get WA, and have no idea why. My program handles spaces and blank lines correctly and I think my LCS algorithm does not have a flaw. Please help.

Code: Select all

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

char s1[1005];
char s2[1005];
void findLCS();
int main() {
	while(gets(s1) && gets(s2))
		findLCS();
	return 0;
}

void findLCS() {
	int m = strlen(s1)-1;
	int n = strlen(s2)-1;
	int C[m+1][n+1];
	for(int i = 0; i <= m; i++) 
		C[i][0] = 0;
	for(int i = 1; i <= n; i++)
		C[0][i] = 0;
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			if(s1[i] == s2[j])
				C[i+1][j+1] = C[i][j]+1;
			else
				C[i+1][j+1] = (C[i+1][j] > C[i][j+1]) ? C[i+1][j] : C[i][j+1];
		}
	}
	cout << C[m][n] << endl;
}
Thanks in advance.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Dec 05, 2007 11:29 am

Try this:

Code: Select all

a
a
-----
Rio

User avatar
vkubushyn
New poster
Posts: 6
Joined: Fri Oct 26, 2007 11:34 pm
Location: Las Vegas, NV

Post by vkubushyn » Wed Dec 05, 2007 10:33 pm

Hmmm, I get 1 for that input. That's correct isn't it?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Dec 06, 2007 12:58 am

In my platform and in judge's platform, you code outputs 0 with the input.
The newline is "\n", not "\r\n".

-----
Rio

User avatar
vkubushyn
New poster
Posts: 6
Joined: Fri Oct 26, 2007 11:34 pm
Location: Las Vegas, NV

Post by vkubushyn » Thu Dec 06, 2007 2:23 am

Wow, ok it got AC now. Thanks a lot, I'll know not to count the '\r' anymore. I hate it when a correct program gets WA because of a compatibility error ;(.
And then he forked a child, which turned into a zombie, which caused the system to thrash wildly!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10405 - Longest Common Subsequence

Post by Obaida » Sun Jul 27, 2008 10:50 am

Why I got WA?

Code: Select all

Problem Solved
Last edited by Obaida on Fri Sep 05, 2008 9:06 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

Re: 10405 - Longest Common Subsequence

Post by apurba » Tue Sep 02, 2008 10:29 pm

maximum string length is 1000.........check it

Code: Select all

keep dreaming...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10405 - Longest Common Subsequence

Post by Obaida » Fri Sep 05, 2008 9:11 am

Thank you i got accepted before.
Best of luck. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10405 - Longest Common Subsequence

Post by ashish_thakur » Mon Dec 22, 2008 9:55 pm

Why is it giving run time error please help?

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


int
LCSlength(char *seq1, char *seq2){

int len1 = strlen(seq1);
int len2 = strlen(seq2);
if(!(len1 && len2))
return 0;

int C[len1][len2];
int i=0,j=0;
int cond=0;
for(;i<len2;i++)
if(!cond)
cond=C[0]=(seq1[0]==seq2);
else
C[0]=cond;

cond=0;
for(;j<len1;j++)
if(!cond)
cond=C[j][0]=(seq1[j]==seq2[0]);
else
C[j][0]=cond;

for(i=1;i<len1;i++)
for(j=1;j<len2;j++)
if (seq1==seq2[j])
C[j] = C[i-1][j-1] + 1;
else
C[j] = C[j-1]>C[i-1][j]?C[j-1]:C[i-1][j];

return C[len1-1][len2-1];
}


int main(){

char seq1[1005];
char seq2[1005];
while(strlen(gets(seq1))&& strlen(gets(seq2)))
printf("%d\n",LCSlength(seq1,seq2));
return 0;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10405 - Longest Common Subsequence

Post by mf » Tue Dec 23, 2008 11:21 am

gets() returns NULL on end-of-file.
strlen expects a non-NULL pointer, and so it crashes when gets() passes NULL to it.

Post Reply

Return to “Volume 104 (10400-10499)”