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

Implement the physat algorithm, The first assignment in this course require... 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

Computer applicatios, What are the features of an expert system What are the features of an expert system

Dijkstras algorithm, Djikstra's algorithm (named after it is discovered by ... 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, Deletion Algorithm for dequeue Step 1:... 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 not have running time of o (n2), Which sorting al... Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

B – trees, B-trees are special m-ary balanced trees utilized in databases s... 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-

Context sensitive f1 help on a field, In what ways we can get the context s... 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

Road transport booking system, what algorithms can i use for the above titl... 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, How can the third d... 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

Algorithm, Write an algorithm for compound interest. Write an algorithm for compound interest.