The space bar has stopped working on Katt’s cellphone, so that now the words in his mail messages all run together with no spaces. Actually, the punctuation marks are not working either. So Katt wishes you to develop an algorithm that, provided a string X, computer efficiently how many ways X can be broken up into the sequence of words. You may utilize Katt’s word tester as the “black box” subroutine, so that provided a pair i and j ≥ i, you may test in constant time whether x_i,x_i+1 • • • x_j is a valid word. Also analyze the running time of your algorithm.