Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- P = 177
- MOD = 192073433
- def main():
- strings = input().split(",")
- string_hashes = []
- max_string_length = 0
- for string in strings:
- hashes = [0]
- for i in range(len(string)):
- hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
- string_hashes.append(hashes)
- max_string_length = max(max_string_length, len(string))
- pows = [1] # P ** i
- for i in range(max_string_length + 1):
- pows.append(pows[-1] * P % MOD)
- sorted_indices = list(range(len(strings)))
- sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))
- disabled_hashes = set()
- answers = [None for _ in strings]
- for i in sorted_indices:
- string = strings[i]
- hashes = string_hashes[i]
- hash_to_be_disabled = []
- min_length = len(string) + 1
- for x in range(len(string)):
- for y in range(x, len(string)):
- substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
- substr_hash = (substr_hash + MOD) % MOD
- hash_to_be_disabled.append(substr_hash)
- if substr_hash not in disabled_hashes and min_length > (y - x + 1):
- min_length = y - x + 1
- answers[i] = (x, y)
- disabled_hashes.update(hash_to_be_disabled)
- print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))
- if __name__ == "__main__":
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement