Find longest repeat prefix of string - linear time algorithm, Data Structure & Algorithms

1. A string s is said to be periodic with a period α, if s is αk for some k>2. (Note that αk is the string formed by concatenating k times.) A DNA sequence s is called a tandem repeat if it is periodic. Given a DNA sequence s, determine if it is periodic, and if so, the values for α and k. Note that there could be more than one period for a periodic string. In such a case, you need to report the shortest period.

2. A non-empty string β is called a repeat prefix of a string s if ββ is a prefix of s. Give a linear time algorithm to find the longest repeat prefix of s.

Hint: Think of using lca queries.

Posted Date: 4/2/2013 5:17:36 AM | Location : United States







Related Discussions:- Find longest repeat prefix of string - linear time algorithm, Assignment Help, Ask Question on Find longest repeat prefix of string - linear time algorithm, Get Answer, Expert's Help, Find longest repeat prefix of string - linear time algorithm Discussions

Write discussion on Find longest repeat prefix of string - linear time algorithm
Your posts are moderated
Related Questions
Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

reverse the order of elements on a stack S using two additional stacks using one additional stack

The ?-Notation (Lower Bound) This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n 0 and

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,

Q. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I


What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

explain quick sort algorithm