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
Q. Write down an algorithm to insert a node in between any two nodes in a linked list         Ans. Insertion of a the node after the given element of the listis as follows

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

We have discussed that the above Dijkstra's single source shortest-path algorithm works for graphs along with non-negative edges (like road networks). Given two scenarios can emerg

In this unit, we learned the data structure arrays from the application point of view and representation point of view. Two applications that are representation of a sparse matrix

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

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

AVL trees and the nodes it contains must meet strict balance requirements to maintain O(log n) search time. These balance restrictions are kept maintained via various rotation func

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

write an algorithm for the gpa of six students