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

Terminology used for files structures, Given are the definitions of some im... Given are the definitions of some important terms: 1) Field: This is an elementary data item characterized by its size, length and type. For instance, Name

Design and test a reference array, Instructions Design and test a r... Instructions Design and test a reference array. Reference array stores the references to user supplied objects of different types. Just think it as a heterogeneous array wh

Determine the importance of array, Determine the importance of array Ar... Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

Implement a min-heap, Description A heap is an efficient tree-based data... Description A heap is an efficient tree-based data structure that can be used as a priority queue. Recall that the abstract data type of a priority queue has the following opera

The best average behaviour, The best average behaviour is shown by  Qui... The best average behaviour is shown by  Quick Sort

Hasing and indexing, differentiate between indexing and hashing in file org... differentiate between indexing and hashing in file organization

Types of tree ?, Binary: Each node has one, zero, or two children. This ... Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

Randomized algorithm, need an expert to help me with the assignment need an expert to help me with the assignment

Monthly loan calculator using amortization table, Please give the code to t... Please give the code to this programme

Process of post-order traversal, Post-order Traversal This can be done ... Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.