Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import defaultdict
- def main():
- def find_hash(string, base, mod):
- if len(string) == 0:
- return 0
- if len(string) == 1:
- return ord(string) % mod
- hsh = ord(string[0]) * base
- for i in range(1, len(string)-1):
- hsh %= mod
- hsh += ord(string[i])
- hsh *= base
- return (hsh + ord(string[-1])) % mod
- a, M = 1000000007, 18446744073709551616
- L, k = list(map(int, input().split()))
- s = input()
- enters = defaultdict(list)
- reduced_h = find_hash(s[:L], a, M) # уменьшаемое
- deductible = s[0] # вычитаемое
- enters[reduced_h].append(0) # словарь {хэш строки: [индексы начал этой строки]}
- power_L = a ** (L - 1) % M # это множитель символа из начала строки, он всегда в этой степени
- for i in range(1, len(s) - L + 1):
- # новый хэш = уменьшаемое (предыдущий хэш) минус вычитаемое первый символ предыущей строки,
- # который всегда в степени L - 1 плюс символ, появившейся в конце
- h = ((reduced_h - ord(deductible) * power_L) * a % M + ord(s[L + i - 1])) % M
- # обновляем уменьшаемое и вычитаемое
- deductible = s[i]
- reduced_h = h
- # добавляем в словарь по ключу-хэшу индекс вхождения строки, от которой посчитан ключ-хэш
- enters[h].append(i)
- for item in enters:
- if len(enters[item]) >= k:
- print(enters[item][0], end=' ')
- if __name__ == '__main__':
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement