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

Array implementation of a queue, Since the stack is list of elements, the q... Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Frequency count, i:=1 while(i { x:=x+1; i:=i+1; } i:=1 while(i { x:=x+1; i:=i+1; }

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

Fibonnaci series, pseudo code for fibonnaci series pseudo code for fibonnaci series

Programs, Develop a program that accepts the car registration( hint: LEA 43... Develop a program that accepts the car registration( hint: LEA 43242010)

Determine the effect of ruby in implementation of string, Determine the eff... Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

What do you understand by structured programming, What do you understand by... What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Generic doubly linked list, Your objective is to write a generic doubly lin... Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

Link list, algorithm for multiplication of two sparse matrices using link l... algorithm for multiplication of two sparse matrices using link list

Using array to execute the queue structure, Q. Using array to execute the q... Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.