# Определение количества различных подстрок с использованием хеш-функции.
# Пусть дана строка S длиной N, состоящая только из маленьких латинских букв.
# Требуется найти количество различных подстрок в этой строке.
import hashlib


def count_substrings(s):
    # будущие подстроки во избежание дублирования будут храниться в множестве
    h_subs = set()
    # перебираем все возможные отрезки строки
    for i in range(len(s)):
        for j in range(1, len(s) + 1):
            if s[i:j]:
                h_subs.add(hashlib.sha1(s[i:j].encode('utf-8')).hexdigest())
    # возвращаем значение за вычетом единицы, потому что в множество попала уникальным элементом и целая строка
    return len(h_subs) - 1


s1 = input(f'Введите, пожалуйста, строку, состояющую из латинских букв:   ')
print(f'Количество подстрок в Вашей строке: {count_substrings(s1)}')
