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

Ask an Expert

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

Write your message here..

Related Questions

Explain in brief the asymptotic notations, Question 1 Write the different ... 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

Frequency count, i:=1 while(i { x:=x+1; i:=i+1; } i:=1 while(i { x:=x+1; i:=i+1; }

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

Non-recursive implementation of binary tree traversals, As we have seen, as... 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

Bubble sort, #question bubble sort.. #question bubble sort..

Illustrate the intervals in mathematics, Illustrate the intervals in mathem... 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 ≤

Stack, using a program flowchart design a program to illustrate pop and pus... using a program flowchart design a program to illustrate pop and push operation

Explain b- tree, B- Tree  A B-tree of order m is an m-way true in which... 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, Two broad classes of ... Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Worst case and average case, Worst Case: For running time, Worst case runn... 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