Page 2 of 3
Posted: Mon Feb 09, 2004 5:23 pm
by sidky
Actually, this is not a Longest Common Subsequence problem. Instead, you have to find the longest common substring of the given DNA strands.
the output for angga888's input:
not
Posted: Thu Feb 12, 2004 9:53 am
by angga888
Thanks sidky, I get AC now.
Regards,
angga888
Posted: Tue Jul 27, 2004 5:34 am
by jackie
Yes. sidky is right. The problem isn't decribled clearly,.
I got AC using DP algorithm.
Pay attention to the blank line and two complete different strings in the input file which make the answer is "No common sequence.".
Posted: Fri Sep 02, 2005 12:19 am
by Jan
Can anyony give me some difficult test cases?
Thanks in advance.
Posted: Fri Sep 02, 2005 12:19 pm
by Jan
Finally got Accepted.
Thanks.
Posted: Fri Sep 02, 2005 12:24 pm
by Jan
Did you handle the blank lines correctly?
Just try the following input output set.
Input:
Code: Select all
atgc
tga
atgc
gctg
at
gcc
t
tgc
atc
gggg
actccccccc
tcccccccccccccc
aattggcc
ttggggcc
aattggcc
ccggttaa
a
t
a
ata
tat
aaatttcccggg
gggaaacccttt
aaatttcc
tttttttttatttttaattcc
aaaggaaaaa
aacaa
Code: Select all
tg
gc
tg
No common sequence.
No common sequence.
No common sequence.
No common sequence.
tccccccc
ggcc
ttgg
aa
cc
gg
tt
No common sequence.
No common sequence.
No common sequence.
at
ta
aaa
ccc
ggg
ttt
aatt
attt
ttcc
aa
Hope it helps.
760 WA
Posted: Tue Jan 30, 2007 7:41 am
by pineapple
I always get WA at 0.07*s.Who can tell me what's wrong with my code?Thanks very much!
The following is my code:
Posted: Tue Jan 30, 2007 4:59 pm
by Vexorian
Posted: Fri Feb 09, 2007 9:45 am
by pineapple
OK!Thanks for your help.
But I also can handle the blank lines,and give the same output.
I have no idea why I always get WA.
Posted: Sat Feb 10, 2007 1:58 pm
by Vexorian
I can't think of anything besides that there shouldn't be a \n at the end of the output but just between different results, but that should be PE not WA.
For what is worth, dp was not needed in this problem.
Posted: Sun Feb 11, 2007 2:58 pm
by pineapple
Thanks for your help.It's my careless,I write:
instead of
But I have corrected it the day before yesterday.You can see my code above.Now I still get many WAs,maybe there is someting wrong in my algorithm?Please help me.
If you have get Accepted,could you show me some cases I can't handle?
Posted: Sun Feb 11, 2007 3:06 pm
by rio
Vexorian wrote:For what is worth, dp was not needed in this problem.
I agree. Using DP makes it complex.
How about using more simple approach?
Re:
Posted: Mon Oct 12, 2009 8:28 pm
by jurajz
rio wrote:How about using more simple approach?
I don't know, if my approach is more simple, but I solved this problem with trie.
Re: 760 - DNA Sequencing
Posted: Fri May 18, 2012 11:25 am
by magurmach
Used SA and then kept all the ans in a set so that it gets ordered in lexicographical way.
But getting WA!
Please help.
code link:
Removed after AC
Re: 760 - DNA Sequencing
Posted: Thu May 31, 2012 1:13 pm
by amyth469
@magurmach
What did you do to get AC ?
I also have the same problem as you had.
please help..