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
Using the concept of structures, write a program to assign passenger seats in an airplane. Assume a small airplane with seats numbered as follows: 1 A B C D 2 A B C D 3 A

XML Publishing. Consider the following relational data: Products: pid Name Price Description 323 gizmo

Advantages of visual basic programming language Visual Basic is an exclusive selection language published by Microsoft Company, so programs published in Visible Basic cannot, e

Redundant sequence identification: Given a set of k DNA sequences, S = { s 1, s 2, ... ,  s k } give an optimal algorithm to identify all sequences that are completely contained

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

1. Write a program that reads a minimum of three command line arguments and displays the program's results. a. Command Line arguments:  i. The first argument will be the program

I need help with some simple matlab statements

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

Expertsmind brings you unique solution in java assignments Networking The term system selection represents composing applications that do across several gadgets (computers

Write a program to show ten buttons with five possible colors: red, green, orange, yellow, blue. When the user clicks on a button, its color must advance to the next color, or go b