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

Explain the goto statement - computer programming, Explain the Goto Stateme...

Explain the Goto Statement - Computer Programming? The goto statement is employed to alter the normal sequence of program execution by transferring control to some other part o

Assembly language programm , these 8 numbers (15, 20, 25, 30, 35, 40, 45, a...

these 8 numbers (15, 20, 25, 30, 35, 40, 45, and 50) with using conditional jump

Adding new features to a simple shell implementation, You will be working o...

You will be working on creating both a realistic project environment and on adding new features to a simple shell implementation provided in shell.tar.z. After you un-tar it, let's

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

Genetic diseases, Genetic Diseases Problem Description Many human di...

Genetic Diseases Problem Description Many human diseases could be controlled by the knowledge of the gene's structure and pattern. The human gene could be represented by fou

C programming, write a function that raises an integer to a positive intege...

write a function that raises an integer to a positive integer power. call the function x_to_the_n taking two integer arguments x and n. have the function return a long int, which r

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

Shell script to convert decimal no. to any other base no., Normal 0 ...

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

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