10829 - L-Gap Substrings

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

10829 - L-Gap Substrings

Post by filigabriel » Tue Mar 08, 2005 12:33 pm

Any hint for solving this problem ??

In the worst case (a string with 50,000 same character), the solution is greater than 500,000,000 L-GAP. O.K. We can manage that case.

I think, even using KMP's algrithm is not possible count all L-GAPs in time

Please, help.

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Sat Mar 12, 2005 10:28 am

hi filigabriel,
I can't understand the porblem. Can you help me? :D

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Sat Mar 12, 2005 9:07 pm

A g-Gap is defined as a string in the form UVU such that |V| = g.

For example: AALLAA is a 2-Gap taking U = AA and V = LL.
furthermore is 4-GAP because of U = A and V = ALLA and |V| = 4,
finally is not a 6-GAP, because U can not be empty.

The problem consists in given a string S, and a positive integer G, count all substrings S' in S such that S' is a G-Gap.

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Sun Mar 13, 2005 3:44 am

Thanks filigabriel, i got the problem. :D You got any hints????


Regards,
Ibrahim

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Thu Mar 17, 2005 11:16 am

Hmm.. still no hint? I also stuck in this problems..

any help will be appreciated :P

Thx :)

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Mon May 02, 2005 10:22 am

Any hints ?
I could only get an O(n^2) method, but it surely got TLE.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Fri Aug 26, 2005 4:23 am

hmm...

suffix tree is not bad

we can count L-Gap strings during making the tree

I think it should work

I also wonder how the guys on ranklist deal this problem..

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Aug 26, 2005 11:23 pm

I only solved this problem because for an bioinformatics course I had read a paper which described an algorithm how to find branching tandem repeats. I modified this algorithm for this problem. I know that the problemsetter had a different solution, he told me it is something with divide and conquer and extended kmp (knuth morris pratt algorithm) (but I don't know what he meant with extended).

polch
New poster
Posts: 1
Joined: Tue Aug 30, 2005 12:27 am

Post by polch » Tue Aug 30, 2005 12:54 am

!!!!!!!!!!!!!!! SPOILER - ATTENTION !!!!!!!!!!!!!!!!!!!!!!!!!!!







Hi,I solved this task using KMR + binary search in O(n*(logn)^2).

For each k being length of U I counted all subwords UVU of text in O(n/k*logk). (|V|=g)

Adrian, how fast (asympt.) algo have you got?

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10829 - L-Gap Substrings

Post by serur » Thu May 28, 2009 3:58 pm

to Adrian: did you store all the (i,D) pairs -- L-gap tandem repeats -- explicitly? I'm going to use an O(nlogn) algo for branching tandem repeats

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10829 - L-Gap Substrings

Post by serur » Fri May 29, 2009 8:50 pm

Never mind, the question above is silly: we are asked to find the number of occurences, not the number of distinct substrings.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10829 - L-Gap Substrings

Post by serur » Sat May 30, 2009 9:11 am

I find all branching tandem repeats with gap 0 <= g <= L and length > L-g in O(L*n*log(n)).
Specifically, for

Code: Select all

bbaabaaaaa$
my code finds pairs

Code: Select all

(6,10), (3,7), (8,10), (4,6), (7,9) and (2,6)
but fails to find

Code: Select all

(6,8),
because the corresponding tandem repeat (g = 0) is not branching.
The question is: how to handle non-branching repeats in O(nlogn)?

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10829 - L-Gap Substrings

Post by serur » Sun May 31, 2009 11:30 am

for the testcase

Code: Select all

s = a^n
the output size is

Code: Select all

(n-L-1) + (n-L-3) + (n-L-5) + ...,
which amounts to O(n^2). Now, given we can find all branching tandem repeats in O(nlogn), how
to handle non-branching tandem repeats?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10829 - L-Gap Substrings

Post by serur » Sat Jun 06, 2009 8:05 pm

Well, with Adrian's help I managed to get AC with an O(|GAP|n(logn)^2) algo, and I can't see as yet the way of shortening this to O(nlogn).
My code is 580 :wink: lines long, pure C code.
Many thanks to Adrian and to Rujia!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

luyuncheng
New poster
Posts: 1
Joined: Wed Oct 31, 2012 5:21 pm

Re: 10829 - L-Gap Substrings

Post by luyuncheng » Thu Apr 04, 2013 9:43 am

can anyone give me some hint for this problem?i don't know how to solve this? as i think ,may be suffix array,but i don't know how to deal with the gap?can anyone help me? thanks very much! my email:luyuncheng@sina.com

Post Reply

Return to “Volume 108 (10800-10899)”