LevMukoseev

Untitled

Oct 24th, 2020
659
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. a = input()
  2. ceil = 10**9 + 7
  3. const = 31
  4. degree = [0]*len(a)
  5. degree[0] = const
  6.  
  7. for i in range(1, len(a)):
  8.     degree[i] = degree[i - 1] * const
  9.  
  10. base_hash = [0]*len(a)
  11. base_hash[0] = ord(a[0])
  12. for i in range(1, len(a)):
  13.     base_hash[i] = base_hash[i - 1] + ord(a[i]) * degree[i]
  14.    
  15. result = 0
  16.  
  17. for lenght in range(1, len(a) + 1):
  18.     hashes = set()
  19.     for index in range(len(a) - lenght + 1):
  20.         cur_hash = base_hash[index + lenght - 1]
  21.         if index > 0:
  22.             cur_hash -= base_hash[index - 1]
  23.             # cur_hash //= degree[index - 1]
  24.         cur_hash *= degree[len(a) - index - 1]
  25.         hashes.add(cur_hash)
  26.     result += len(hashes)
  27. print(result)
RAW Paste Data