Задача 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

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.txt', '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()