Advertisement
Guest User

Untitled

a guest
Dec 9th, 2021
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.46 KB | None | 0 0
  1. P = 177
  2. MOD = 192073433
  3.  
  4. def main():
  5.     strings = input().split(",")
  6.     string_hashes = []
  7.     max_string_length = 0
  8.     for string in strings:
  9.         hashes = [0]
  10.         for i in range(len(string)):
  11.              hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
  12.         string_hashes.append(hashes)
  13.         max_string_length = max(max_string_length, len(string))
  14.  
  15.     pows = [1] # P ** i
  16.     for i in range(max_string_length + 1):
  17.         pows.append(pows[-1] * P % MOD)
  18.  
  19.     sorted_indices = list(range(len(strings)))
  20.     sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
  21.    
  22.     disabled_hashes = set()
  23.     answers = [None for _ in strings]
  24.     for i in sorted_indices:
  25.         string = strings[i]
  26.         hashes = string_hashes[i]
  27.  
  28.         hash_to_be_disabled = []
  29.         min_length = len(string) + 1
  30.         for x in range(len(string)):
  31.             for y in range(x, len(string)):
  32.                 substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
  33.                 substr_hash = (substr_hash + MOD) % MOD
  34.                 hash_to_be_disabled.append(substr_hash)
  35.                 if substr_hash not in disabled_hashes and min_length > (y - x + 1):
  36.                     min_length = y - x + 1
  37.                     answers[i] = (x, y)
  38.  
  39.         disabled_hashes.update(hash_to_be_disabled)
  40.  
  41.     print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
  42.  
  43.  
  44. if __name__ == "__main__":
  45.     main()
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement