Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. import sys
  2.  
  3.  
  4. def count_bits(s):
  5. return [s.count("0"), s.count("1")]
  6.  
  7.  
  8. # 1 - in case where a >= b
  9. # 0 - otherwise
  10. def compare_bits_count(a, b):
  11. if a[0] >= b[0] and a[1] >= b[1]:
  12. return 1
  13. else:
  14. return 0
  15.  
  16.  
  17. def subtract_bits_count(a, b):
  18. return [a[0] - b[0], a[1] - b[1]]
  19.  
  20.  
  21. def z_function(s):
  22. n = len(s)
  23. l = 0
  24. r = 0
  25. z = [0 for x in range(n)]
  26. for i in range(1, n):
  27. z[i] = max(0, min(r - i, z[i - l]))
  28. while i + z[i] < n and s[z[i]] == s[i + z[i]]:
  29. z[i] += 1
  30. if i + z[i] > r:
  31. l = i
  32. r = i + z[i]
  33. return z
  34.  
  35.  
  36. s = input()
  37. t = input()
  38.  
  39. s_bits_count = count_bits(s)
  40. t_bits_count = count_bits(t)
  41.  
  42. if compare_bits_count(s_bits_count, t_bits_count) == 0:
  43. print(s)
  44. sys.exit()
  45.  
  46. result = t
  47. s_bits_count = subtract_bits_count(s_bits_count, t_bits_count)
  48.  
  49. r = ""
  50.  
  51. z = z_function(t)
  52. for i in range(len(t) // 2, len(t)):
  53. if z[i] == len(t) - i:
  54. r = t[len(t) - i:]
  55. r_bits_count = count_bits(r)
  56. break
  57.  
  58. if len(r) == 0:
  59. r = t
  60. r_bits_count = t_bits_count
  61.  
  62. while s_bits_count[0] > 0 or s_bits_count[1] > 0:
  63. if compare_bits_count(s_bits_count, r_bits_count) == 1:
  64. result += r
  65. s_bits_count = subtract_bits_count(s_bits_count, r_bits_count)
  66. else:
  67. result += '0' * s_bits_count[0]
  68. result += '1' * s_bits_count[1]
  69. break
  70.  
  71. print(result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement