Задача 2

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import re

def find_all(s1, s2):
    res = []
    st = 0
    st = s2.find(s1, st)
    while st != -1:
        res.append(st)
        st += len(s1)
        st = s2.find(s1, st)
    return res

# делители числа n
def get_factors(n):
    res = []
    for i in range(1, n + 1):
        if n % i == 0:
            res.append(i)
    return res

def decrypt(c, k):
    n = 26
    t = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    k *= len(c) // len(k) + 1
    m = ''
    for i in range(len(c)):
        cj = t.find(c[i])
        kj = t.find(k[i])
        mj = (cj + n - kj) % n
        m += t[mj]
    return m

def v_decrypt(dictionary):
    s1 = input()

    # избавляемся от всех лишних символов в строке
    s2 = ''
    for c1 in s1:
        if c1.isalpha():
            s2 += c1

    # приводим всю строку к одному регистру
    s2 = s2.upper()

    # рассматриваем 3-граммы, 4-граммы и 5-граммы
    grs = set()
    for n in [3, 4, 5]:
        for i in range(len(s2) - n + 1):
            gr = s2[i:i + n]
            if s2.count(gr) > 1:
                grs.add(gr)
    grs = list(grs)

    # определяем расстояния между n-граммами
    ds = set()
    for gr in grs:
        d = find_all(gr, s2)
        for i in range(1, len(d)):
            for j in range(i):
                ds.add(d[i] - d[j])

    # находим делители этих чисел
    c = {}
    for d in ds:
        fs = get_factors(d)
        fs.remove(1)
        for f in fs:
            c[f] = c.get(f, 0) + 1
    list_c = list(c.items())
    list_c.sort(key=lambda c: -c[1])
    c = dict(list_c)

    # буквы по убыванию частоты встречаемости в английском языке
    en = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'

    lens = set()

    f = open(dictionary, 'r')
    lines = []
    for line in f:
        lens.add(len(line.strip()))
        lines.append(line.strip())

    p = re.compile(r"[A-Za-z]+")
    w1 = p.search(s1).group(0)

    # выделение символов
    for k in c.keys():
        cs = []
        for i in range(k):
            s3 = s2[i::k]
            mx_o = -1
            cs.append([])
            for j in range(ord('A'), ord('Z') + 1):
                s4 = decrypt(s3, chr(j))
                nu = list(en)
                nu.sort(key=lambda elem: (-s4.count(elem), -en.find(elem)))
                nu = ''.join(nu)
                o = len(set(en[:6]) & set(nu[:6]))
                o += len(set(en[-6:]) & set(nu[-6:]))
                if o == mx_o:
                    cs[-1].append(chr(j))
                if o > mx_o:
                    mx_o = o
                    cs[-1] = [chr(j)]
        ks = []
        queue = ['']
        while queue:
            v = queue.pop(0)
            if len(v) < len(cs):
                for w in cs[len(v)]:
                    queue.append(v + w)
            else:
                m = decrypt(s2, v)
                w2 = m[:len(w1)]
                if w2 in lines:
                    print(v.lower())
                    i = 0
                    res = ''
                    for c2 in s1:
                        if c2.isalpha():
                            if c2.islower():
                                res += m[i].lower()
                            else:
                                res += m[i]
                            i += 1
                        else:
                            res += c2
                    print(res)
                    quit()