Algorithm to compute a minimum cover time and space, Programming Languages

Given strings s1 and s2 of lengths m and n respectively, a minimum cover of s1 by s2 is a decomposition s1 = w1w2 .... wk, where each wi is a non-empty substring of s2 and k is minimized. Eg., given s1 = accgtatct and s2 = cgtactcatc, there are several covers of s1 by s2 possible, two of which are:

(i) cover1: s1 = w1w2w3w4 (where w1 = ac, w2 = cgt, w3 = atc, w4 = t) , and

(ii) cover2: s1 = w1w2w3w4w5 (where w1 = ac, w2 = c, w3 = gt, w4 = atc, w5 = t).

However, only cover1 is a minimal cover. Give an algorithm to compute a minimum cover (if one exists) in O (m + n) time and space. If a minimum cover does not exist your algorithm should state so and terminate within the same time and space bounds. Give a brief justification of why you think your algorithm is correct - meaning, how it guarantees finding the minimial cover (if one exists).

Posted Date: 3/28/2013 6:25:52 AM | Location : United States







Related Discussions:- Algorithm to compute a minimum cover time and space, Assignment Help, Ask Question on Algorithm to compute a minimum cover time and space, Get Answer, Expert's Help, Algorithm to compute a minimum cover time and space Discussions

Write discussion on Algorithm to compute a minimum cover time and space
Your posts are moderated
Related Questions
code for using tree view control and fill it with database

What are Attributes in HTML langauge? A few tags have attributes. An attribute is a name, followed through an = sign, followed by the value. For instance, to make a centered H1

Im having problems with my php / mysql code. I am trying to make it so it looks for an asset Number and if it is in the shop if the asset is in the database but is not in the shop

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Question 1 Explain the history of Internet Question 2 What are the advantages of DHTML? Question 3 Explain the concept of DOM Question 4 How does AJAX work

Write a Fortran LOGICAL FUNCTION, called "is_prime", which determines if a given integer value is a prime number or not (A prime number is a natural number which has only two disti

I need help with making a assembly program that uses Hoffman''s coding scheme to compress a text file.

You must implement the control mechanism for the robot arm so that it can safely move the blocks from the source pile to their destination, without colliding with any obstacles or

code for using tree view control and fill it with database using asp.net and language vb.net

Example :  Solve the following differential equation. y (3)   -  12 y''+48 y' + 64 y = 12 - 32 e -8t + 2 e 4t Solution :    We first require the complementary solution