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
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

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 Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

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 is shown by  Quick Sort

differentiate between indexing and hashing in file organization

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

need an expert to help me with the assignment


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