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
What are the expression trees? Represent the below written expression using a tree. Give a relevant comment on the result that you get when this tree is traversed in Preorder,

Q. The two Binary Trees are said to be similar if they are both empty or if they are both non- empty and left and right sub trees are similar. Write down an algorithm to determine

Enumerate about the Data structure An arrangement of data in memory locations to signify values of the carrier set of an abstract data type. Realizing computational mechanis


Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Q. Implement a stack making use of the linked list. Show the PUSH and POP operations both. A n s . Stack implemantation using linked list # include # include

Describe Binary Search Tree (BST)? Make a BST for the given sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the obtained tree in Preorder, Inord

Determine the Disjoint of division method A polygon is disjoint from the viewport if the x- and y-extents of the polygon do not overlap the viewport anywhere. In this case; reg

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also