Given strings s_{1} and s_{2} of lengths m and n respectively, a minimum cover of s_{1} by s_{2} is a decomposition s1 = w_{1}w_{2} .... wk, where each w_{i} is a non-empty substring of s_{2} and k is minimized. Eg., given s_{1} = accgtatct and s_{2} = cgtactcatc, there are several covers of s_{1} by s_{2} possible, two of which are:
(i) cover_{1}: s_{1} = w_{1}w_{2}w_{3}w_{4} (where w_{1} = ac, w_{2} = cgt, w_{3} = atc, w_{4} = t) , and
(ii) cover_{2}: s_{1} = w_{1}w_{2}w_{3}w_{4}w_{5} (where w_{1} = ac, w_{2} = c, w_{3} = gt, w_{4 }= atc, w_{5} = t).
However, only cover_{1} 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).