<jupyter_start><jupyter_text>1. Определение количества различных подстрок с использованием хеш-функции. Пусть дана строка S длиной N. Например, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке. Для решения задачи рекомендую воспользоваться алгоритмом sha1 из модуля hashlib или встроенную функцию hash()<jupyter_code>from collections import defaultdict


def find_substr(s):
    hash_dict = defaultdict(int)
    str_len = len(s)
    summ = 0
    for n in range(1, str_len): # последовательное увеличение длинны подстроки
        for i in range(str_len - n + 1):  # сдвиг каретки для взятия подстроки
            sub = hash(s[i:i+n])
            if sub not in hash_dict:  # Если подстрока встретилась первый раз
                for j in range(str_len - n + 1):  # сдвиг каретки для поиска подстроки
                    if sub == hash(s[j:j+n]):
                        hash_dict[sub] += 1
                        summ += 1
    return len(hash_dict), summ


my_string = 'beep boop beer'
res = find_substr(my_string)
print(f'Кол-во уникальных подстрок {res[0]}, кол-во найденных подстрок {res[1]}')<jupyter_output>Кол-во уникальных подстрок 90, кол-во найденных подстрок 104<jupyter_text>2. Закодируйте любую строку (хотя бы из трех слов) по алгоритму Хаффмана.<jupyter_code>from collections import defaultdict

def my_huffman(input_str):
    def _make_dict_list(s):  # модификация из прошлой задачи
        hash_dict = defaultdict(int)

        str_len = len(s)
        for i in range(str_len):  # сдвиг каретки для взятия подстроки
            sub = s[i:i + 1]
            if sub not in hash_dict:  # Если подстрока встретилась первый раз
                for j in range(str_len):  # сдвиг каретки для поиска подстроки
                    if sub == s[j:j + 1]:
                        hash_dict[sub] += 1 #посчет сколько раз встречается
        return hash_dict


    def _make_tree_nodes(nodes, label, result, prefix = ''):
        childs = nodes[label]
        tree = {}
        if len(childs) == 2:
            tree['0'] = _make_tree_nodes(nodes, childs[0], result, prefix+'0')
            tree['1'] = _make_tree_nodes(nodes, childs[1], result, prefix+'1')
            return tree
        else:
            result[label] = prefix
            return label


    def _bin_code(_vals):
        vals = _vals.copy()
        nodes = {}
        for n in vals.keys():
            nodes[n] = []

        while len(vals) > 1:
            s_vals = sorted(vals.items(), key=lambda x:x[1])
            a1 = s_vals[0][0]
            a2 = s_vals[1][0]
            vals[a1+a2] = vals.pop(a1) + vals.pop(a2)
            nodes[a1+a2] = [a1, a2]
        code = {}
        root = a1+a2
        tree = _make_tree_nodes(nodes, root, code)
        return code, tree


    def _encode(s, code):
        res = []
        for t in s:
            res.append(code[t])
        return res


    code, tree = _bin_code(_make_dict_list(input_str))

    return _encode(input_str, code), code, tree


result = my_huffman('beep boop beer!')
print(f'encoded str {result[0]}, \ncode_dict: {result[1]}, \ncodetree: {result[2]}')<jupyter_output>encoded str ['00', '01', '01', '100', '101', '00', '110', '110', '100', '101', '00', '01', '01', '1110', '1111'], 
code_dict: {'b': '00', 'e': '01', 'p': '100', ' ': '101', 'o': '110', 'r': '1110', '!': '1111'}, 
codetree: {'0': {'0': 'b', '1': 'e'}, '1': {'0': {'0': 'p', '1': ' '}, '1': {'0': 'o', '1': {'0': 'r', '1': '!'}}}}
{'fraction_non_alphanumeric': 0.13946162657502864, 'fraction_numerical': 0.03436426116838488, 'mean_word_length': 2.5247225025227045, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '360072', 'license': 'MIT', 'n_tokens_mistral': 1366, 'n_tokens_neox': 1392, 'n_words': 339, 'path': 'marathon_day8.ipynb', 'repo_name': 'fakecoinbase/sweetpandslashAlgorithms', 'size': '3492'}