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

Special matrices, Special Matrices There are some "special" matrices o...

Special Matrices There are some "special" matrices out there which we may use on occasion. The square matrix is the first special matrix.  A square matrix is any matrix that s

Created xml document using the css stylesheet, After studying the concept, ...

After studying the concept, terminology, and implementation of CSS stylesheets, create a stylesheet to accompany your solutions to Question 1. A rich collection of styles should be

#Linux, Hi Dehren, Below is the assessment question for the linux:  Task Y...

Hi Dehren, Below is the assessment question for the linux:  Task Your job in this assignment is to create two Virtual machines each running a different but the latest distribution

String cost, A string S is said to be "Super ASCII", if it contains the cha...

A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the asci

Shell script to compare that given two files are same or not, Normal 0 ...

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

Design and create a new class, You are to design and create a new class cal...

You are to design and create a new class called SelectCallDataDialog, which opens by clicking browse  buttons for selection of ringtones,  vibrations or leds. Depending on which th

Ajax and php, would you like to see some of my code. I am trying to do an a...

would you like to see some of my code. I am trying to do an add friend request. when I view my friends page I click on the add button. with ajax I want the script to send over the

Write c sharp application to read a data, A number of simple student record...

A number of simple student records are written to a text file. The format of some typical linesshould be - Task (1): Using a text editor, create a file with 10 such reco

What is an authentication subsystem, Question: (i) All Security authen...

Question: (i) All Security authentication mechanism that run on the TRU64 Unix Operating system run under the Security Integration Architecture (SIA ) layer. Explain with di

Design program that presents animation of the solar system, Figure is a rep...

Figure is a representation of the solar system. In a basic model of the same concentric orbits planets rotate around the sun. The closer the Planet in less time Sun completes a ful

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