Advertisement
giGii

4_L

Apr 23rd, 2022
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.84 KB | None | 0 0
  1. from collections import defaultdict
  2.  
  3.  
  4. def main():
  5.  
  6.     def find_hash(string, base, mod):
  7.         if len(string) == 0:
  8.             return 0
  9.         if len(string) == 1:
  10.             return ord(string) % mod
  11.         hsh = ord(string[0]) * base
  12.         for i in range(1, len(string)-1):
  13.             hsh %= mod
  14.             hsh += ord(string[i])
  15.             hsh *= base
  16.         return (hsh + ord(string[-1])) % mod
  17.    
  18.    
  19.     a, M = 1000000007, 18446744073709551616
  20.     L, k = list(map(int, input().split()))
  21.     s = input()
  22.     enters = defaultdict(list)
  23.    
  24.     reduced_h = find_hash(s[:L], a, M)  # уменьшаемое
  25.     deductible = s[0]  # вычитаемое
  26.     enters[reduced_h].append(0)  # словарь {хэш строки: [индексы начал этой строки]}
  27.     power_L = a ** (L - 1) % M  # это множитель символа из начала строки, он всегда в этой степени
  28.    
  29.     for i in range(1, len(s) - L + 1):
  30.         # новый хэш = уменьшаемое (предыдущий хэш) минус вычитаемое первый символ предыущей строки,
  31.         # который всегда в степени L - 1 плюс символ, появившейся в конце
  32.         h = ((reduced_h - ord(deductible) * power_L) * a % M + ord(s[L + i - 1])) % M
  33.         # обновляем уменьшаемое и вычитаемое
  34.         deductible = s[i]
  35.         reduced_h = h
  36.         # добавляем в словарь по ключу-хэшу индекс вхождения строки, от которой посчитан ключ-хэш
  37.         enters[h].append(i)
  38.     for item in enters:
  39.         if len(enters[item]) >= k:
  40.             print(enters[item][0], end=' ')
  41.  
  42.  
  43. if __name__ == '__main__':
  44.     main()
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement