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

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

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

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

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

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

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

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,

using a program flowchart design a program to illustrate pop and push operation