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

Algorithm to insert a node in between any two nodes, Q. Write down an algor... 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

Depth first traversal, A depth-first traversal of a tree visits a nodefirst... 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

Implement an algorithm to simulate car re-organizing, Design  and implement... 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

Graphs with negative edge costs, We have discussed that the above Dijkstra'... 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

Data structure arrays, In this unit, we learned the data structure arrays f... 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

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

Java, Ask consider the file name cars.text each line in the file contains i... 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 tree rotations, AVL trees and the nodes it contains must meet strict ba... 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

State warnock algorithm, Warnock's Algorithm An interesting approach to... 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

Algorithm, write an algorithm for the gpa of six students write an algorithm for the gpa of six students