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
'This program compares interest rates between two banks and determines the best bank 'Eric Weber, Adam Litchfield, Eric Romero, Sarah, Alex, Amy '10/5/12 'Lab #4 Problem 42 'CSC

Below is an example of an invalid XHTML page. Your goal is to rewrite the code so that: No deprecated/obsolete tags are being used All elements are nested correctly (i.e

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

Use recursion to de ne a function position which has as input an integer, a character and a string and returns the result of inserting the character in the string at the position s

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

Write a Prolog predicate  has_duplicates(L)  that is true if list  L  contains duplicated elements (that is at least 2 copies of an element). For instance: ?- has_duplicates([a,

Task: This assignment is about writing programmes and Web Services in C#: 1) Develop a console programme that reads a sequence of integer numbers from the console and sorts

showing work Ubuntu system or either opensuse

Create a Money data structure that is made up of amount and currency.  (a) Write a constructor for this data structure   (b)  Create accessors for this data structure (c)