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
For this assignment you will read a file expression.txt and create an expression tree. The expression will be a valid infix expression with the all the necessary parentheses so tha

Real Distinct Eigenvalues Under this case we'll have the real, distinct eigenvalues l 1 ≠l 2 ≠l 3 a and their related eigenvectors, ?h 1 , ?h 2 and  ?h 3   are guarantee

In this section we need to take a brief look at systems of differential equations which are larger than 2 x 2. The problem now is not like the first few sections where we looked at

how to store an url in a dartabase(sql server 2005)? (or) create table b(url what is the datatype for url?

We'll start this section off with the material which most text books that will cover in this section. We will take the matter from the Second Order chapter and expand this out to n

Create a single page that demonstrates an XHTML form. The form should include all the fields you feel are necessary for submitting an order of books and must include at least one

VARIATION OF PARAMETERS - HIGHER ORDER DIFFERENTIAL EQUATIONS We now require taking a look at the second method of finding a particular solution to a differential equation

The next major set of tasks to tackle are delete and update. Version control systems typically version updates to a ?le and only store the differences between the ?les. Two system

write c++ source code to find the number of digits in a given integer? pls ans