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
Question 1 Write the different characteristics of an algorithm Question 2 Explain in brief the asymptotic notations Question 3 Write an algorithm of insertion sort and e

i:=1 while(i { x:=x+1; i:=i+1; }

the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

#question bubble sort..

Illustrate the intervals in mathematics Carrier set of a Range of T is the set of all sets of values v ∈ T such that for some start value s ∈ T and end value e ∈ T, either s ≤

using a program flowchart design a program to illustrate pop and push operation

B- Tree  A B-tree of order m is an m-way true in which  1)  All leaves are on the similar level 2)  All internal nodes except the root have at most m-1(non-empty) childre

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo