⚙️ Алгоритмы · 20 вопросов · ~45 мин · ⏱ Таймер 45:00 · Сложный ·

Алгоритмы обработки строк

Эффективный поиск строки опирается на уже известные совпадения: префиксная функция подсказывает безопасный откат, хеш позволяет быстро сравнить подстроки, а динамическая таблица собирает минимальную последовательность правок. Тест включает периодические строки, коллизии, ошибки границ и восстановление операций.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Какое значение pi[4] для строки "ababa"?

s = "ababa"
pi = [0] * len(s)
for i in range(1, len(s)):
    j = pi[i - 1]
    while j > 0 and s[i] != s[j]:
        j = pi[j - 1]
    if s[i] == s[j]:
        j += 1
    pi[i] = j
print(pi[4])

1 4 2 3

Вопрос 2 из 20

Какой массив pi получится для "aaaa"?

s = 'aaaa'
pi = [0] * len(s)
for i in range(1, len(s)):
    j = pi[i - 1]
    while j > 0 and s[i] != s[j]:
        j = pi[j - 1]
    if s[i] == s[j]:
        j += 1
    pi[i] = j
print(pi)

[0,1,2,3] [0,0,0,0] [1,2,3,4] [0,1,1,1]

Вопрос 3 из 20

Что означает pi[i]?

Количество различных символов в префиксе s[0..i] без учёта их порядка Длину самого длинного собственного префикса s[0..i], который является его суффиксом Позицию следующего полного совпадения шаблона в тексте после индекса i Полиномиальный хеш префикса s[0..i], нормализованный по модулю

Вопрос 4 из 20

К какому j нужно откатиться при несовпадении?

i = current_text_position
j = matched_prefix_length
while j > 0 and text[i] != pattern[j]:
    j = ...
if text[i] == pattern[j]:
    j += 1
# Нужно выбрать выражение вместо многоточия.

pi[j] + 1 pi[j - 1] 0 всегда j - 1

Вопрос 5 из 20

Строка длины n имеет период p=n−pi[n−1]. Когда она полностью состоит из повторов блока длины p?

p=n-\pi_{n-1},\quad n\bmod p=0

Когда pi[n−1]=0 всегда Когда n делится на p Когда n нечётно Когда p больше n

Вопрос 6 из 20

На каком индексе начинается первое совпадение?

text = "ababcababa"
pattern = "ababa"
print(text.find(pattern))

6 0 2 5

Вопрос 7 из 20

Как вычислить начало найденного шаблона в KMP?

for i, char in enumerate(text):
    while j > 0 and char != pattern[j]:
        j = prefix[j - 1]
    if char == pattern[j]:
        j += 1
    if j == len(pattern):
        start = ...
        occurrences.append(start)
        j = prefix[j - 1]

i + len(pattern) i - len(pattern) + 1 i - j - 1 j - i

Вопрос 8 из 20

Почему KMP работает за O(n+m)?

Линейность получается из предварительной сортировки текста и шаблона по кодам символов Он сравнивает каждый символ текста со всеми символами шаблона, но делает это одним циклом Индекс текста не возвращается назад, а j откатывается по заранее вычисленным границам Оценка O(n+m) верна только для уникальных символов, когда откаты j не нужны

Вопрос 9 из 20

Какой дефект у наивного поиска?

def find_first(text, pattern):
    for start in range(len(text) - len(pattern)):
        if text[start:start + len(pattern)] == pattern:
            return start
    return -1

Срез всегда пустой Нельзя сравнивать строки через == Не проверяется последняя допустимая позиция старта Проверяется одна лишняя позиция

Вопрос 10 из 20

Как искать шаблон через Z-функцию одной строки?

Построить матрицу переходов между символами и искать путь длины pattern Сравнить длины pattern и text, после чего проверить позиции с одинаковыми индексами Отсортировать символы текста и шаблона, затем искать совпадающие непрерывные блоки Построить pattern + разделитель + text и искать значения Z, равные длине pattern

Вопрос 11 из 20

Как получить хеш подстроки [l,r) из префиксных хешей в простой схеме?

def substring_hash(left, right, prefix, powers, base, mod):
    # prefix[i] — хеш s[:i] по схеме
    # prefix[i + 1] = (prefix[i] * base + code(s[i])) % mod
    length = right - left
    return ...

# Нужно выбрать выражение вместо многоточия.

(prefix[right] * powers[right-left] - prefix[left]) % mod (prefix[right-left] * powers[left]) % mod (prefix[right] - prefix[left]) % mod (prefix[right] - prefix[left] * powers[right-left]) % mod

Вопрос 12 из 20

Почему после вычитания берут % mod?

value = (prefix[right] - prefix[left] * powers[right-left]) % mod

Чтобы полностью исключить коллизии: разным строкам получить разные остатки Чтобы превратить остаток в индекс первого символа рассматриваемой подстроки Чтобы длины сравниваемых строк стали одинаковыми перед вычислением хеша Разность может быть отрицательной, модуль возвращает канонический остаток

Вопрос 13 из 20

Что означает совпадение двух одиночных хешей?

Повторное вычисление тем же основанием и модулем устранит возможность коллизии Хотя бы один символ различается, иначе хеши не могли бы совпасть Строки могут быть равны, но одного совпавшего хеша недостаточно из-за коллизий Строки равны, если вместе с хешем совпала их длина

Вопрос 14 из 20

Как надёжнее обработать совпавшие хеши в системе, где ошибка недопустима?

def definitely_equal(a, b):
    hash_a = polynomial_hash(a)
    hash_b = polynomial_hash(b)
    if hash_a != hash_b:
        return False
    # Нужно выбрать надёжную заключительную проверку.
    return ...

result = definitely_equal(first_text, second_text)

После совпадения хешей выполнить окончательное посимвольное сравнение Посчитать второй независимый хеш и считать пару совпадений абсолютным доказательством равенства Повторно вычислить тот же хеш с теми же основанием и модулем Сравнить длины, а также первый и последний символы строк

Вопрос 15 из 20

Зачем заранее вычислять степени p?

H(l,r)=pref_r-pref_l\,p^{r-l}

Чтобы получать хеш любой подстроки за O(1) после префиксной подготовки Чтобы хранить вторую копию текста, умноженную на очередные степени основания Чтобы перед вычислением хешей отсортировать символы по степеням в полиноме Чтобы подобрать простой модуль, перебирая степени p до первого простого значения

Вопрос 16 из 20

Каково расстояние Левенштейна между "cat" и "cut"?

a = 'cat'
b = 'cut'
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

for i in range(len(a) + 1):
    dp[i][0] = i
for j in range(len(b) + 1):
    dp[0][j] = j

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        cost = 0 if a[i - 1] == b[j - 1] else 1
        dp[i][j] = min(dp[i - 1][j] + 1,
                       dp[i][j - 1] + 1,
                       dp[i - 1][j - 1] + cost)
print(dp[-1][-1])

3 1 0 2

Вопрос 17 из 20

Какой переход используется при совпадающих последних символах?

if a[i - 1] == b[j - 1]:
    dp[i][j] = ...

dp[i-1][j-1] dp[i][j-1]+1 0 независимо от префиксов dp[i-1][j]+1

Вопрос 18 из 20

С какой соседней ячейкой связана операция удаления символа из a?

dp[i−1][j−1] без цены dp[i+1][j] dp[i][j−1]+1 dp[i−1][j]+1

Вопрос 19 из 20

Как инициализировать первую строку и столбец таблицы?

def edit_distance(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

    # Здесь нужно заполнить dp[i][0] и dp[0][j],
    # прежде чем считать остальные клетки.

    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,
                           dp[i][j - 1] + 1,
                           dp[i - 1][j - 1] + cost)
    return dp[-1][-1]

Всё единицами dp[i][0]=i и dp[0][j]=j dp[i][0]=j и dp[0][j]=i Всё нулями

Вопрос 20 из 20

Что дополнительно нужно хранить для восстановления последовательности операций?

dp_{i,j}=\min\{del,ins,sub\}

Длины строк и их последние символы; остальной путь восстанавливается по ним Для каждой строки таблицы лишь позицию минимальной ячейки Выбранного предшественника или тип операции для каждой ячейки Только итоговую стоимость dp[n][m], потому что она однозначно задаёт предыдущие клетки

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу