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
The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

What are the features of an expert system

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

Deletion Algorithm for dequeue Step 1: [check for underflow]   If front = 0 and rear = 0   Output "underflow" and return Step 2: [delete element at front end]   If front

Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

B-trees are special m-ary balanced trees utilized in databases since their structure allows records to be added, deleted & retrieved with guaranteed worst case performance. A B-

In what ways we can get the context sensitive F1 help on a field?' Data element documentation. Data element additional text in screen painter. Using the process on help r

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

How can the third dimension be displayed on the screen The main problem in visualization is the display of three-dimensional objects and scenes on two-dimensional screens. How

Write an algorithm for compound interest.