Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- def count_bits(s):
- return [s.count("0"), s.count("1")]
- # 1 - in case where a >= b
- # 0 - otherwise
- def compare_bits_count(a, b):
- if a[0] >= b[0] and a[1] >= b[1]:
- return 1
- else:
- return 0
- def subtract_bits_count(a, b):
- return [a[0] - b[0], a[1] - b[1]]
- def z_function(s):
- n = len(s)
- l = 0
- r = 0
- z = [0 for x in range(n)]
- for i in range(1, n):
- z[i] = max(0, min(r - i, z[i - l]))
- while i + z[i] < n and s[z[i]] == s[i + z[i]]:
- z[i] += 1
- if i + z[i] > r:
- l = i
- r = i + z[i]
- return z
- s = input()
- t = input()
- s_bits_count = count_bits(s)
- t_bits_count = count_bits(t)
- if compare_bits_count(s_bits_count, t_bits_count) == 0:
- print(s)
- sys.exit()
- result = t
- s_bits_count = subtract_bits_count(s_bits_count, t_bits_count)
- r = ""
- z = z_function(t)
- for i in range(len(t) // 2, len(t)):
- if z[i] == len(t) - i:
- r = t[len(t) - i:]
- r_bits_count = count_bits(r)
- break
- if len(r) == 0:
- r = t
- r_bits_count = t_bits_count
- while s_bits_count[0] > 0 or s_bits_count[1] > 0:
- if compare_bits_count(s_bits_count, r_bits_count) == 1:
- result += r
- s_bits_count = subtract_bits_count(s_bits_count, r_bits_count)
- else:
- result += '0' * s_bits_count[0]
- result += '1' * s_bits_count[1]
- break
- print(result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement