# ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
# Число Фибоначии
# Дерево Фибоначчи. O(Fib_n)

# ===============================================
# Плохая реализаци поиска числа Фибоначчи!!!


# def fib(n):
#     if n <= 1:
#         return n
#     return fib(n-1) + fib(n-2)

# Плохая реализаци поиска числа Фибоначчи!!!
# ===============================================

def fibonachi(n):
    fib = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]
# ===============================================
# Траектория движения кузнечика.
# Сколько различных траекторий допрыгать из 1 в N ?,
# при условии что можно прыгать только вперед:
# 1. на +1
# 2. на +2
# 3. на +3
# введем дополнительные условия трактории, запретим некоторые клетки для посещения.

# По формуле K_n = K_n-3 + K_n-2 + K_n-1


def count_trajectories(n, allowed: list):
    k = [0, 1, int(allowed[2])] + [0] * (n-3)
    for i in range(3, n-1):
        if allowed[i]:
            k[i] = k[i-1] + k[i-2] + k[i-3]

# минимальная стоимость достижения клетки
# price[i] - за посещение i
# cost[i] - минимально возможная стоимость достижения клетки i
# при условии что можно прыгать только вперед:
# 1. на +1
# 2. на +2
# float("-inf") - минус бесконечность


def count_min_cost(n, price: list):
    c = [float("-inf"), price[1], price[1] + price[2]] + [0] * (n-2)
    for i in range(3, n+1):
        c[i] = price[i] + min(c[i-1], c[i-2])
    return c[n]


# ДВУМЕРНЫЕ МАССИВЫ
# Два пути создания массива:
# 1. ЛИНЕАРИЗАЦИЯ двумерного массива
# (A(i,j), где N-строк, М-элементов в строке) = A[i*M+j)

# 2. Создание списка списков
# ======================================
# НЕ ПРАВИЛЬНО!!!
# a = [[0] * M] * N  # ТАК НЕЛЬЗЯ!!!
# ======================================
# ПРАВИЛЬНО!
# a = [[0]*m for i in range(n)]
# ======================================
# НАИБОЛЬШАЯ ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ
def lcs(a, b):
    f = [[0] * (len(b)+1) for i in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                f[i][j] = 1 + f[i-1][j-1]
            else:
                f[i][j] = max(f[i-1][j], f[i][j-1])
    print(f)
    print(f[-1][-1])
    return f[-1][-1]


# a = [8, 1, 5, 9, 7, 8]
# b = [5, 2, 4, 6, 3, 9]
# lcs(a, b)
# ======================================
# (ДЛИНА) НАИБОЛЬШАЯ ВОЗРАСТАЮЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ
def gis(a):
    f = [0]*(len(a)-1)
    for i in range(1, len(a)+1):
        m = 0
        for j in range(1, i):
            if a[i] > a[j] and f[j] > m:
                m = f[j]
        f[i] = m + 1
    return len(f)


# ======================================
# (ДИСКРЕТНЫЙ) АЛГОРИТМ УКЛАДКИ РЮКЗАКА
# ======================================
# АЛГОРИТМ ЛЕВЕНШТЕЙНА - Редакционное расстояние между строками.
# (через ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ)
# A = "колокол" n
# B = "молоко" m
# Сколько нудно допустить орфографических ошибок в А, что бы получилось В ?
# Ошибки:
# 1. Перепутали символ
# 2. Вставили лишний символ
# 3. Потеряли нужный символ
# Существует траектория, по которой можно осуществить редакционную правку
# Функция F[i][j] - минимальное расстояние между срезами (от начала до i-го символа) А[:i]
# и B[:j] (от начала до j-го символа)
# Ответ: F[n][m]

def levenstein(a, b):
    f = [[i+j if i*j == 0 else 0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                f[i][j] = f[i-1][j-1]
            else:
                f[i][j] = 1+min(f[i-1][j], f[i][j-1], f[i-1][j-1])
    return f[len(a)][len(b)]


# a = "колокол"
# b = "молоко"
# print(levenstein(a, b))
# ======================================
# Проверка равенства строк


def equal(a, b):
    if len(a) != len(b):
        return False
    for i in range(len(a)):
        if a[i] != b[i]:
            return False
    return True

# ======================================
# Поиск подстроки в строке


def search_substring(s, sub):
    for i in range(0, len(s)-len(sub)):
        if equal(s[i:i+len(sub)], sub):
            print(i)

# s = "abacabacbabacfabacabacabbbabavdabacabac"
# sub = "abac"
# search_substring(s, sub)
# ======================================
# Префкис функции ПИ строки
# Собственный суффикс - суффикс, не равный самой строке
# ПИ-строки - длина максимального собственного суффикса, который является префиксом
# ПИ-строки[i] - префикс функция среза строки s[:i]
# ======================================
# Алгоритм Кнута Мориса Прата (КМП)
# Z-функция.
