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
how to create a screen for messages for a data transmission system

how to make a program using vb?seriously i don''t know

You should use the BToolkit to produce the answers to the questions below. Where applicable, please use the machine names and identifier names suggested in the question to help me

The following are required for this lesson: Complete the Project "Adding New Payments," which is the Karate Payments that includes the Adding New Payments, Deleting Payments,

I need help putting this into a flowchart constant c as Integer = 3500 Constant CALORIESTOOUNCE as Integer = 219 Declare Sex as Character Declare Age as Integer Declare Weight as I

Windows Workflow Foundation Microsoft windows Work-flows foundation (WF) is an Enthusiasm technological innovation that provides an API, an in-process workflow website, and a rehos

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 reader-writer problem can be stated as follows: A shared memory location can be concurrently read by any number of tasks, but when a task must write to the shared memory locati

The idea of this section is not to do anything new along with a series solution problem.  Instead this is here to exemplify that moving in a higher order differential equation does

Need help with a cobol program.