Interleaving: Difference between revisions

Line 67:

(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 ~~fewer~~ ''x'' and one ~~more~~ ''y'' than ''c''.

(c) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''Y''' and ''c''('''XZ''', '''YZ''')'''X'''. If the sizes of ''b''('''XZ''', '''YZ''')'''Y''' and ''c''('''XZ''', '''YZ''')'''X''' are different we are done. If they are the same, we have that ''by'' and ''cx'' subtend the same interval in ''w'', hence ''b'' has one more ''x'' and one fewer ''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''.

(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''~~xbx~~'' = ''xb'xx'', ~~continue scooting to the left until you find a~~ ''y'' ~~to the left, then same case as~~ (~~ii)~~, (2).

(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''xby'' = ''xb'xy'', and we have ‖''p''('''XZ''', '''YZ''')'''X'''‖ as a fourth interval size.

(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', ~~we have ‖~~''p''~~('''XZ''', '''YZ''')'''Y'''‖ as a fourth interval size~~.

(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', continue scooting to the left until you find an ''x'' to the left.

(i), (2) => ''b'' = ''b'y'', ''p'' = ''xb' '', we have ‖''p''('''XZ''', '''YZ''')'''X'''‖ as a fourth interval size.

@@ Line 67: / Line 67: @@
 (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 fewer ''x'' and one more ''y'' than ''c''.
+(c) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''Y''' and ''c''('''XZ''', '''YZ''')'''X'''. If the sizes of ''b''('''XZ''', '''YZ''')'''Y''' and ''c''('''XZ''', '''YZ''')'''X''' are different we are done. If they are the same, we have that ''by'' and ''cx'' subtend the same interval in ''w'', hence ''b'' has one more ''x'' and one fewer ''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''.
-(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''xbx'' = ''xb'xx'', continue scooting to the left until you find a ''y'' to the left, then same case as (ii), (2).
+(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''xby'' = ''xb'xy'', and we have ‖''p''('''XZ''', '''YZ''')'''X'''‖ as a fourth interval size.
-(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', we have ‖''p''('''XZ''', '''YZ''')'''Y'''‖ as a fourth interval size.
+(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', continue scooting to the left until you find an ''x'' to the left.
 (i), (2) => ''b'' = ''b'y'', ''p'' = ''xb' '', we have ‖''p''('''XZ''', '''YZ''')'''X'''‖ as a fourth interval size.