Interleaving: Difference between revisions
| Line 67: | Line 67: | ||
(d) is similar to (a). | (d) is similar to (a). | ||
(b) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y'''. If the sizes of ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''w'', hence ''b'' has one | (b) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y'''. If the sizes of ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''w'', hence ''b'' has one fewer ''x'' and one more ''y'' than ''c''. | ||
By scooting ''bx'' one letter to the left in ''w'', we find either (i) ''xb'' or (ii) ''yb''. The {{pipe}}''b''{{pipe}}-letter prefix ''p'' of this subword subtends either the same interval as (1) ''b'' or (2) ''c''. | By scooting ''bx'' one letter to the left in ''w'', we find either (i) ''xb'' or (ii) ''yb''. The {{pipe}}''b''{{pipe}}-letter prefix ''p'' of this subword subtends either the same interval as (1) ''b'' or (2) ''c''. | ||