You are not logged in. Please login at www.codechef.com to post your questions!

×

dna sequence matching problem....

i am getting a trouble finding an approach to solve this problem....

input-output sequences are as follows

input1 : aaagctgctagag

output1 : a3gct2ag2


input2 : aaaaaaagctaagctaag

output2 : a6agcta2ag

input nsequence can be of 10^6 characters and largest continuous patterns will be considered. For example in input2 "agctaagcta" it will not be agcta2gcta but it will be "agcta2".

any help appreciated.

Extra Examples :

1) input aabbaabb output is aabb2 not a2b2a2b2

2) input aaaaaaaaabbbbbbbbbaaaaaaaaabbbbbbbbb output is a9b9a9b9 not aaaaaaaaabbbbbbbbb2

It shows that smaller the encode it is most likely to be an answer.

asked 01 Jun '13, 14:37

saj1919's gravatar image

4★saj1919
915511
accept rate: 0%

edited 02 Jun '13, 14:52


-1

I would read the input string character by character, and look if the next one is the first of a suffix of already processed data. If so, i increment a counter for this chunk, else i just continue. I don't know if this method is correct, but that would be my first approach.

link

answered 02 Jun '13, 00:59

cyberax's gravatar image

3★cyberax ♦
3.4k21955
accept rate: 20%

edited 02 Jun '13, 00:59

@rakeshbubli143: why downvoting ?

(02 Jun '13, 22:41) cyberax ♦3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×643
×86
×63
×38

question asked: 01 Jun '13, 14:37

question was seen: 3,105 times

last updated: 02 Jun '13, 22:41