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

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.

Determine the disjoint of division method, Determine the Disjoint of divisi... Determine the Disjoint of division method A polygon is disjoint from the viewport if the x- and y-extents of the polygon do not overlap the viewport anywhere. In this case; reg

Logic circuits, the voltage wave forms are applied at the inputs of an EX-O... the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

Explain insertion procedure into a b-tree, Ans: I nsertion into the B... Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th

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

Progrrame, how to write a code for for a company , for calculate the salary... how to write a code for for a company , for calculate the salary pay

Graph, For the following graph find the adjacency matrix and adjacency list... For the following graph find the adjacency matrix and adjacency list representation of the graph.

Stack, implement multiple stacks ina single dimensional array. write algori... implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

Deletion of a node from a binary search tree, The algorithm to delete any n... The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

Stack, using a program flowchart design a program to illustrate pop and pus... using a program flowchart design a program to illustrate pop and push operation