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

Depth first search, DEPTH FIRST SEARCH (DFS) The approach adopted into ... DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

LINKED LIST, HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENT... HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?

Define tractable and intractable problems, Define tractable and intractable... 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

Random searching, write aprogram for random -search to implement if a[i]=x;... write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

String manipulation, what is string manipulation? what is string manipulation?

Define binary search technique, Binary search technique:-  This techniq... Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

Recursion, differences between direct and indirect recursion differences between direct and indirect recursion

Number of leaf nodes in a complete binary tree, The number of leaf nodes in... The number of leaf nodes in a complete binary tree of depth d is    2 d

Explain the method of overlapping and intersecting, Overlapping or Interse... Overlapping or Intersecting A polygon overlaps or intersects the current background if any of its sides cuts the edges of the viewport as depicted at the top right corner of th

What do you understand by tree traversal, What do you understand by tree tr... What do you understand by tree traversal? The algorithm walks by the tree data structure and performs some computation at everynode in the tree. This process of walking by the