Given strings s₁ and s₂ of lengths m and n respectively, a minimum cover of s₁ by s₂ is a decomposition s1 = w₁w₂ .... wk, where each w_i is a non-empty substring of s₂ and k is minimized. Eg., given s₁ = accgtatct and s₂ = cgtactcatc, there are several covers of s₁ by s₂ possible, two of which are:

(i) cover₁: s₁ = w₁w₂w₃w₄ (where w₁ = ac, w₂ = cgt, w₃ = atc, w₄ = t) , and

(ii) cover₂: s₁ = w₁w₂w₃w₄w₅ (where w₁ = ac, w₂ = c, w₃ = gt, w₄ = atc, w₅ = t).

However, only cover₁ 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).