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

Shell script for to change & display system prompt and path, Normal 0 ...

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

Write a shell script to find the factorial of a given number, W.A.S.S to fi...

W.A.S.S to find the factorial of a given number. Program # W.A.S.S to find the factorial of a given number.    echo -e "enter number:\c"            #  \c Suppress trailing n

What is .net?, What is .NET? It is a foundation fairly neutral structure...

What is .NET? It is a foundation fairly neutral structure. Is a coating between the son and the selection language? It can handle many selection dialects, such as VB.NET,

Matrix, Write a function named prob2.m which creates and returns an N×N ide...

Write a function named prob2.m which creates and returns an N×N identity matrix. An identity matrix is a square matrix with values of one on the main diagonal and zeros in all off-

Vbs, Add macros to MS word 2010 according to A PARTICULAR FORMAT

Add macros to MS word 2010 according to A PARTICULAR FORMAT

Check a file for spelling errors, Normal 0 false false fals...

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

Matlab fem, I need a program that writes the first column of the matrix. T...

I need a program that writes the first column of the matrix. The numbers in this column follow the pattern below: 1. Numbers start at 1 and count up to ''nels'' in increments of

COS-101: INTRODUCTION TO COMPUTERS, COS-101: INTRODUCTION TO COMPUTERS PRO...

COS-101: INTRODUCTION TO COMPUTERS PROJECT DESCRIPTION The Computer Fundamentals Project provides you with a chance to apply what you have learned about computer fundamentals to

Visual basic a simple help, hello there, I making a program for the collage...

hello there, I making a program for the collage but I got stuck at one point, I have a timmer that moves object pnl with the pnl.left function, but I want it when it gets to end of

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