760

junjieliang · Post by **junjieliang** » Wed Dec 12, 2001 9:48 am

Isn't this problem LCS? Then why is it for the first input the output is "tg", instead of "tgc"?

Thanx

.

necropower · Post by **necropower** » Mon Mar 25, 2002 10:01 pm

hey guys , i noticed that the input and the output for the first case is kind of odd.
it shows "atgc","tgc"
but the output is "tg"
isnt it "tgc"???
can u explain that?

thanks
[[]]'s Necropower

.. · Post by .. » Tue Mar 26, 2002 1:24 pm

In the problem description:

So, the longest common sequence in the two strands atgc and tga is tg.

Is the sample input have typo??
My accetped program will output "tgc "for "atgc" and "tgc".........

necropower · Post by **necropower** » Tue Mar 26, 2002 1:55 pm

(i am using @ instead of interrogation, my keyboard is broken)

did u get accepted@
can u tell me your main idea of searching in strings@ my program is too slow and i didnt find a better way to search on the strings...

thanks,
Necropower

.. · Post by .. » Tue Mar 26, 2002 5:50 pm

hm.....
I think my algorithm is quite "brute force"

let's say there is string A, B

First check if the last char of B is a substring of A,
if yes, copy the last 2 chars and check again
if no, copy the last 2nd char to check......

just run like this......

Stefan Pochmann · Post by **Stefan Pochmann** » Wed Mar 27, 2002 7:37 am

Hmm... I'm confused... is it the longest common subsequence problem or the longest common substring problem? Of course there's no real definition in the problem, but it sounds like the subsequence problem. On the other hand, your approach sounds more like the substring problem? What is it?

.. · Post by .. » Wed Mar 27, 2002 8:10 am

Yes, this question is to find sub-string...

Den Raskovalov · Post by **Den Raskovalov** » Tue Apr 30, 2002 5:17 pm

Note: Sequence should be continious!
Also there is error in sample output.

Caesum · Post by **Caesum** » Tue Jul 16, 2002 9:48 pm

The question says:

If there are more than one test cases, it must be a blank line between two consecutive, both in input and output files.

So I use 3 gets's to read the two strings and the next blank, however the next 'blank' line is not always a blank line ? Can anyone confirm the input format for me please ?

Ivan Golubev · Post by **Ivan Golubev** » Tue Jul 16, 2002 10:13 pm

I've used

Code: Select all

while(scanf("%s %s\n", s1, s2) == 2) ...

and it was enough to get PE.

gvcormac · Post by **gvcormac** » Wed Jul 17, 2002 12:17 am

It is a common *substring* problem (I agree that the problem is ill-specified.)

The fastest possible algorithm (linear time) is to build a suffix tree. If you search the web you'll find references and code.

Eric3k · Post by **Eric3k** » Sat May 10, 2003 3:39 am

Prog 760, DNA sequencing, http://acm.uva.es/p/v7/760.html, in the first input, it has atgc and tgc and the corresponging output tg. However, shouldn't it be tgc?
Thx

negue · Post by **negue** » Mon May 26, 2003 2:09 am

Yes. They probably meant atgc and tga as input.

Can someone give me some clues or i/o samples, because I guess I'm doing it right but I get wa.

Thanks!

angga888 · Post by **angga888** » Thu Jan 15, 2004 4:37 pm

Hi,
I got lot of WA for this problem.
Could someone please tell me the output of this input:

aaaggaaaaa
aacaa

Any tricky I/O for this problem?

Regards,
angga888

sohel · Post by **sohel** » Mon Feb 09, 2004 3:59 pm

I am also getting WA for this problem.

Isn't simply LCS;

I applied LCS and sorted all the answers lexicographically and avoided repetition. Shouldn't it be enough.
Thanx.

OJ Board

760 - DNA Sequencing

760

760?

760 - DNA Sequencing

LCS