The longest Weak repeated substring problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

The longest Weak repeated substring problem

Post by lena »

Suppose S is a string S[1....n], we call a substring P of S weak repeated,if
P=s[i...j] satisfied : there exists another subtring T=s[k...l], T equals to P, and i != k.
can someone give me an answer
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: The longest Weak repeated substring problem

Post by mf »

lena wrote:Suppose S is a string S[1....n], we call a substring P of S weak repeated,if
P=s[i...j] satisfied : there exists another subtring T=s[k...l], T equals to P, and i != k.
Build a suffix tree for string S$, and choose the string corresponding to any deepest non-leaf node as P.
can someone give me an answer
42
But you forgot to tell the question...
Post Reply

Return to “Algorithms”