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
Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

Explain CAM software CAD/CAM software has been recognized as an essential tool in the designing and manufacturing of a product due to its ability to depict the designs and tool

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

Pre-order Traversal The method of doing a pre-order traversal iteratively then has the several steps(suppose that a stack is available to hold pointers to the appropriate nodes

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

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

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

A full binary tree with n leaves have:- 2n -1 nodes.