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

Assignment Help:

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).


Related Discussions:- Algorithm to compute a minimum cover time and space

Help with c assignment, You will design and implement a program that will •...

You will design and implement a program that will • analyse the various characteristics of a maze, represented by a particular coding of its basic con- stituents into numbers store

Jquery, i am stuck on array part from getting response of jquery. anyone co...

i am stuck on array part from getting response of jquery. anyone could help?

Program to present main frame contains of button, The program presents main...

The program presents mainframe contains two button new user, existing user PART ONE: CLICKING ON NEW USER New window appear contains: text field represent username,

Little Man Computer, 1) Write a program that takes an input value (for exam...

1) Write a program that takes an input value (for example, a number 5). The output should be sum of all numbers from 1 to the value input by the user (in this example, the output w

Program to translate a sentence , a) Write a program i_language(Sentence,N...

a) Write a program i_language(Sentence,NewSentence) that translates a sentence to the i-language. In this language all vowels are changed to i and all other characters are kep

Write simple scripts programs , Write 3 somewhat simple scripts / programs ...

Write 3 somewhat simple scripts / programs in any language, combination of languages, and/or software. Please tell me the task you are trying to accomplish in the scripts. Idea

Undetermined coefficients, We now require starting looking into finding a p...

We now require starting looking into finding a particular solution for n th order differential equations. The two ways which we'll be looking at are similar as those which we look

What is linear programming problem, QUESTION 1 (a) (i) What is linear p...

QUESTION 1 (a) (i) What is linear programming problem? (ii) Define and explain the following terms: (1) objective function, (2) decision variable, (3) constraints, (4) feasi

Jsp, how can we get the data from data base to combo box in jsp page dynami...

how can we get the data from data base to combo box in jsp page dynamically

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd