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
1. A readme.txt file with: a. Instructions on how to compile and run your client and server code on the command line. (Also provide shell scripts if the commands are complicated

My kinect hand cursor only works for main menu but when it goes to another page it wouldn''t work.. especially when there is for camera feed

Write a script called 'prob1.m' that solves for the variables y, and z in terms of a user inputed x. The variables y and z are defined as follows: y = x - 30                when

Write a program that will generate 25 DWORD values in the range from +/-50 representing a two dimensional array of size 5 x 5. It should then display the array as a table (5 x 5) b

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

Vacation Envy - Travel and Photo Sharing Website Site Overview- Vacation Envy is a travel as well as photo-sharing site. Make your travel map, share photos and show off al

We now require starting looking into finding a particular solution for n th order differential equations. The two ways which we'll be looking at are similar as those which we look

The aims of this assignment are to:    Provide experience in the use of a modern Integrated Development Environment (specifically NetBeans running on a Linux platform) for t

What is DOM? The Document Object Model is a platform- and language-neutral interface that will allow programs and scripts to dynamically access and update the content, structure an

System.in and System.out should not be used anywhere in the programs except in main and only for testing purposes.  All calculations should be done in a method.  Note:  To use J