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 ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.

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

By scooting ''bx'' one letter to the left in ''s'', we find either (i) ''xb'' or (ii) ''yb''. The |''b''|-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 |''b''|-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).

@@ 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 ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.
+(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 more ''x'' and one fewer ''y'' than ''c''.
-By scooting ''bx'' one letter to the left in ''s'', we find either (i) ''xb'' or (ii) ''yb''. The |''b''|-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 |''b''|-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).