BOTTOM UPandysoft 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:is top-down? or bottom-up?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 ...
thanx in advance
10405 - Longest Common Subsequence
Moderator: Board moderators
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
oh, shame on me
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
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
my profile
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
10405 - i need a worst case input.
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:
Here's my code:
All i need is a complex input to break my code. Preferably not too long, so it isn't too hard to trace ^^.
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
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;
}
Help pls
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.
Thanks in advance.
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;
}
Try this:
-----
Rio
Code: Select all
a
a
Rio
Re: 10405 - Longest Common Subsequence
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.
This may be the address of success.
Re: 10405 - Longest Common Subsequence
maximum string length is 1000.........check it
Code: Select all
keep dreaming...
Re: 10405 - Longest Common Subsequence
Thank you i got accepted before.
Best of luck.
Best of luck.
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
-
- New poster
- Posts: 7
- Joined: Mon Dec 22, 2008 3:00 pm
Re: 10405 - Longest Common Subsequence
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;
}
#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;
}
Re: 10405 - Longest Common Subsequence
gets() returns NULL on end-of-file.
strlen expects a non-NULL pointer, and so it crashes when gets() passes NULL to it.
strlen expects a non-NULL pointer, and so it crashes when gets() passes NULL to it.