760 - DNA Sequencing

[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:

Code: Select all

aa

not

Code: Select all

aaaa  <---- Wrong

[angga888]

Thanks sidky, I get AC now.

Regards,
angga888

[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.".

[Jan]

Can anyony give me some difficult test cases?

Thanks in advance.

[Jan]

Finally got Accepted.

Thanks.

[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

Output:

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.

[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:

Code: Select all

Cut after AC

[Vexorian]

Try Jan's I/O at: http://online-judge.uva.es/board/viewtopic.php?t=2919

[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.

[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.

[pineapple]

Thanks for your help.It's my careless,I write:

Code: Select all

    first==false;

instead of

Code: Select all

    first=false;

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?

[rio]

For what is worth, dp was not needed in this problem.

I agree. Using DP makes it complex.

How about using more simple approach?

[jurajz]

How about using more simple approach?

I don't know, if my approach is more simple, but I solved this problem with trie.

[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

[amyth469]

@magurmach
What did you do to get AC ?
I also have the same problem as you had.
please help..