Programming Taskbook

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024

Поиск подстрок

Все исходные числовые данные в заданиях являются целыми и неотрицательными. Если числовые данные могут принимать нулевые значения, то об этом явно говорится в формулировке задания.

Все исходные строковые данные являются непустыми. Позиции символов в строках нумеруются от 1. Длина строки S обозначается через |S|; длина исходных строк в заданиях не превосходит 100. Через S[i..j] обозначается подстрока S, начинающаяся в позиции i и оканчивающаяся в позиции j (если i > j, то S[i..j] считается пустой строкой). Через S[i], i = 1, …, |S|, обозначается символ строки S, расположенный в позиции i.

При поиске всех вхождений строки-образца P (англ. pattern) в текст T учитываются перекрывающиеся вхождения. Например, для образца P = «aaa» и текста T = «aaaaaa» количество различных вхождений равно 4 (начиная с позиций 1, 2, 3, 4 текста T). Всегда предполагается, что длина образца P не превосходит длины текста T.

Под алфавитом Σ понимается множество символов, в которое входят все символы рассматриваемых строк. Если алфавит Σ в задании не уточняется, то предполагается, что строка может содержать любые символы, отличные от управляющих.

При подсчете сравнений символов предполагается, что логические операции выполняются по сокращенной схеме (например, при вычислении выражения (i < |P|) and (P[i] = x) сравнение символов P[i] и x будет проводиться только в случае, если условие i < |P| окажется истинным).

Описания алгоритмов приводятся по книге Д. Гасфилда «Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология» (СПб.: БХВ-Петербург, 2003), часть I.

Поиск подстрок: базовые понятия и наивный алгоритм

В данной подгруппе заданий вводятся необходимые понятия, связанные с поиском в строке (подстрока, префикс, суффикс), и описываются простейшие алгоритмы поиска (так называемые наивные алгоритмы).

Match1°. Дана строка S и целые числа i, j, не превосходящие длины строки S. Позиции в строке нумеруются от 1. Через S[i..j] обозначается подстрока S, начинающаяся в позиции i и оканчивающаяся в позиции j. Если i > j, то S[i..j] считается пустой строкой (длина пустой строки равна 0). Вывести длину подстроки S[i..j] и все ее символы (в порядке слева направо).

Match2°. Дана строка S и числа i, j, не превосходящие длины строки S. Префиксом строки S называется любая ее подстрока вида S[1..k], k ≤ |S| (|S| обозначает длину строки S). Если префикс строки S является непустым и не совпадает со всей строкой, то он называется собственным префиксом. Вывести количество префиксов подстроки S[i..j], а также длину и символы каждого ее префикса, перебирая префиксы в порядке возрастания их длин, а символы каждого префикса — в порядке слева направо.

Match3°. Дана строка S и числа i, j, не превосходящие длины строки S. Суффиксом строки S называется любая ее подстрока вида S[k..|S|], k ≥ 1 (|S| обозначает длину строки S). Если суффикс строки S является непустым и не совпадает со всей строкой, то он называется собственным суффиксом. Вывести количество суффиксов подстроки S[i..j], а также длину и символы каждого ее суффикса, перебирая суффиксы в порядке убывания их длин, а символы каждого суффикса — в порядке слева направо.

Match4°. Даны строки P, T и число k. Строка P считается образцом (англ. pattern), строка T — текстом, в котором ищется образец. Известно, что длина суффикса строки T, начинающегося в позиции k, больше или равна |P|. Используя посимвольное сравнение, выполняемое слева направо, проверить, входит ли образец P в текст T, начиная с позиции k. Если входит, то вывести True, иначе вывести False. Вывести также количество потребовавшихся сравнений символов.

Match5°. Даны строки P и T. Найти первое вхождение строки P в текст T, используя наивный алгоритм поиска, при котором выполняется посимвольное сравнение P с каждой из подстрок T длины |P|. Подстроки T перебираются слева направо, символы строк также сравниваются слева направо. При каждом сравнении символов (независимо от успешности сравнения) выводить сравниваемый символ строки P. После завершения алгоритма вывести позицию в T, с которой начинается первое вхождение P, или 0, если вхождения отсутствуют.

Match6°. Даны строки P и T. Найти первое вхождение строки P в текст T, используя модификацию наивного алгоритм поиска (см. Match5), при которой подстроки T перебираются слева направо, а посимвольное сравнение строк выполняется справа налево. При каждом сравнении символов (независимо от успешности сравнения) выводить сравниваемый символ строки P. После завершения алгоритма вывести позицию в T, с которой начинается первое вхождение P, или 0, если вхождения отсутствуют.

Match7°. Даны строки P и T. Найти все вхождения строки P в текст T, используя наивный алгоритм поиска (см. Match5). Вывести позиции в T, с которых начинаются вхождения образца P. Вывести также общее количество сравнений символов, которое потребовалось для решения задачи.

Match8°. Даны строки P и T. Найти все вхождения строки P в текст T, используя модификацию наивного алгоритма поиска (см. Match6). Вывести позиции в T, с которых начинаются вхождения образца P. Вывести также общее количество сравнений символов, которое потребовалось для решения задачи.

Основной препроцессинг: базовые понятия и быстрый алгоритм

В данной подгруппе рассматривается один из вариантов предварительной обработки (препроцессинга) строки. Вводятся понятия, связанные с препроцессингом (Z-блоки и строковые характеристики Z_i, r_i, l_i), и описывается быстрый алгоритм препроцессинга, при котором для обработки строки S требуется число сравнений символов, не превосходящее 2|S|.

Рассмотренный вариант препроцессинга используется при описании многих алгоритмов поиска, поэтому он называется основным препроцессингом.

Match9°. Дана строка S и число i (2 ≤ i ≤ |S|). Через Z_i(S) обозначается длина наибольшей подстроки S, которая начинается в позиции i и совпадает с префиксом строки S. Если требуемые подстроки отсутствуют, то Z_i(S) = 0. Используя посимвольное сравнение строк, найти Z_i(S). Вывести найденное значение, а также количество сравнений символов, потребовавшееся для его нахождения.

Match10°. Дана строка S. Z-блоком строки S в позиции i (> 1) называется непустая строка S[i..i + Z_i(S) − 1], т. е. подстрока S, начинающаяся в позиции i > 1 и имеющая ненулевую длину Z_i(S) (определение Z_i(S) см. в Match9). Известно, что в данной строке S имеется хотя бы один Z-блок длины, большей 2. Используя посимвольное сравнение строк и перебирая позиции в порядке возрастания, найти первый из Z-блоков с указанным свойством. Вывести позицию i найденного Z-блока, его длину Z_i(S), а также количество сравнений символов, потребовавшееся для решения задачи.

Match11°. Дана строка S. Используя посимвольное сравнение строк и перебирая позиции в порядке возрастания, найти все Z-блоки строки S (определение Z-блока см. в Match10). Для каждого найденного Z-блока вывести его позицию и длину. Кроме того, вывести количество сравнений символов, потребовавшееся для решения задачи.

Match12°. Дана строка S и число k (2 ≤ k ≤ |S|). Через r_i(S) обозначается крайний правый конец Z-блоков строки S (см. Match10), начинающихся не позднее позиции i строки S, или 0, если требуемые Z-блоки отсутствуют. Таким образом, ненулевое значение r_i(S) можно найти по формуле r_i(S) = max{j + Z_j(S) − 1}, где j меняется от 2 до i, причем Z_j(S) > 0. При этом через l_i(S) обозначается то значение j, на котором достигается указанный выше максимум (если таких значений j несколько, то через l_i(S) обозначается наибольшее из них). Для r_i(S) = 0 значение l_i(S) полагается равным 0. Используя посимвольное сравнение строк для вычисления Z_i(S), найти и вывести r_i(S) и l_i(S), i = 2, …, k. Вывести также общее количество сравнений символов, потребовавшееся для решения задачи.

Match13°. Дана строка S. Описать числовой массив Z для хранения значений Z_i(S) (см. Match9) и числовые переменные R и L. Реализовать первый шаг быстрого алгоритма основного препроцессинга: используя посимвольное сравнение, найти Z₂ и положить начальные значения для переменных R и L равными соответственно r₂(S) и l₂(S) (см. Match12). Оформить алгоритм в виде вспомогательной подпрограммы. Вывести Z₂, R, L и количество сравнений символов, потребовавшееся для их нахождения.

Match14°. Дана строка S, число k (2 < k ≤ |S|) и значения R = r_k−1 и L = l_k−1. Известно, что k > R. Реализовать для данной ситуации k-й шаг быстрого алгоритма основного препроцессинга. Для этого найти Z_k, используя посимвольное сравнение, и положить значения R и L равными соответственно r_k и l_k (R = k + Z_k − 1, L = k, если Z_k > 0; в противном случае R и L не изменяются). Оформить алгоритм в виде вспомогательной подпрограммы. Вывести Z_k, R, L и количество сравнений символов, потребовавшееся для их нахождения.

Match15°. Дана строка S, число k (2 < k ≤ |S|), значения R = r_k−1 и L = l_k−1, а также значения Z_i, i = 2, …, k − 1. Известно, что k ≤ R. Реализовать для данной ситуации k-й шаг быстрого алгоритма основного препроцессинга. При этом учесть, что в силу неравенства k ≤ R подстрока S' = S[k..R] входит в Z-блок S[L..R], который (по определению Z-блока) совпадает с префиксом S[1..Z_L]. Поэтому S' = S[k'..Z_L], где k' = k − L + 1, и, следовательно, подстрока, начинающаяся с позиции k, должна совпадать, по меньшей мере, с префиксом S длины min{Z_k', |S'|} (|S'| = R − k + 1). Если при этом Z_k' < |S'|, то следует положить Z_k = Z_k'; R и L при этом не изменяются. Если же Z_k' ≥ |S'|, то надо выполнить дополнительную проверку, сравнивая до несовпадения символы S[p], начиная с p = |S'| + 1, и S[q], начиная с q = R + 1; если q достигнет значения |S| + 1 или в позиции q ≥ R + 1 обнаружится несовпадение, то следует положить Z_k = q − k, R = q − 1, L = k. В любом случае R и L окажутся равными r_k и l_k соответственно. Оформить алгоритм в виде вспомогательной подпрограммы. Вывести Z_k, R, L и количество сравнений символов, потребовавшееся для их нахождения (при Z_k' < |S'| данное количество будет равно 0).

Match16°. Дана строка S. Найти Z_i(S), i = 2, …, |S|, используя быстрый алгоритм препроцессинга, описанный в Match13–Match15. Вывести найденные Z_i(S), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Поиск с использованием основного препроцессинга

В подгруппе описываются алгоритмы поиска подстрок, использующие рассмотренный ранее основной препроцессинг. Данные алгоритмы позволяют выполнить поиск за линейное время. Это означает, что для нахождения всех вхождений образца P длины n в текст T длины m требуется число сравнений символов, имеющее порядок n + m. Следует заметить, что наивный алгоритм не обеспечивает поиск за линейное время, так как при его реализации может потребоваться количество сравнений, имеющее порядок n·m.

В заданиях данной подгруппы операция сцепления строк обозначается символом «+». При сцеплении строк сохраняется порядок их следования (например, результатом операции «ab» + «cd» является строка «abcd»).

Match17°. Даны строки P и T, не содержащие символ «$». Реализовать быстрый алгоритм поиска всех вхождений P в T, сформировав строку S = P + «$» + T и выполнив для нее основной препроцессинг (см. Match16). Каждому вхождению P в T соответствует значение Z_i(S), равное |P| (очевидно, i > |P| + 1); при этом данное вхождение начинается в позиции i − |P| − 1 строки T. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match18°. Даны строки P и T, не содержащие символ «$». Найти все вхождения P в T, рассматривая строку T как циклическую (после последнего символа строки T опять берется ее первый символ). Для этого сформировать строку S = P + «$» + T + T', где T' = T[1..|P| − 1], и использовать для нее быстрый алгоритм основного препроцессинга (см. Match16). Вывести начальные позиции всех найденных вхождений (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match19°. Даны строки A и B, не содержащие символ «$». Найти наибольший суффикс строки A, который одновременно является префиксом строки B, и вывести его длину (или 0, если требуемый суффикс отсутствует). Для этого сформировать строку S = B + «$» + A и с помощью быстрого алгоритма основного препроцессинга (см. Match16) найти q = max Z_i(S), где i пробегает все значения, для которых r_i(S) = |A| + |B| + 1. Вывести также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match20°. Даны строки A и B одинаковой длины, не содержащие символ «$». Определить, является ли строка B циклическим сдвигом строки A, и при положительном ответе вывести минимальную величину соответствующего левого сдвига (при отрицательном ответе вывести −1). Например, для строк A = «abcd» и B = «bcda» надо вывести значение 1, а для строк A = «aaa» и B = «aaa» — значение 0. Для этого сформировать строку S = A + «$» + B и с помощью быстрого алгоритма основного препроцессинга (см. Match16) найти q = max Z_i(S), где i пробегает все значения, для которых r_i(S) = 2|A| + 1. Если q = 0, то вывести −1, иначе выполнить посимвольное сравнение оставшейся части строк A и B, и, в зависимости от результатов этого сравнения, вывести −1 или величину левого сдвига (эта величина будет определяться через q). Вывести также количество сравнений символов, потребовавшееся при решении задачи.

Метод Кнута–Морриса–Пратта

В данной подгруппе описывается метод Кнута–Морриса–Пратта (метод КМП) и связанные с ним понятия. Метод КМП является одним из наиболее известных быстрых алгоритмов поиска подстрок.

Match21°. Дана строка P и число i (≤ |P|). Через sp_i(P) обозначается длина наибольшего собственного суффикса подстроки P[1..i], который совпадает с префиксом P (обозначение образовано начальными буквами слов «suffix» и «prefix»). Если требуемые суффиксы отсутствуют, то sp_i(P) = 0. Вывести sp_i(P).

Match22°. Дана строка P и число k (≤ |P|). Через sp'_i(P), i = 1, …, |P| − 1, обозначается длина наибольшего собственного суффикса подстроки P[1..i], который совпадает с префиксом P и для которого выполняется дополнительное условие: символы в позициях i + 1 и sp'_i(P) + 1 не равны. Таким образом, sp'_i(P) ≤ sp_i(P) (величина sp_i(P) определена в Match21). В случае i = |P| по определению полагается sp'_|P|(P) = sp_|P|(P). Вывести sp'_i(P) для i = k, …, |P|.

Match23°. Дана строка P и число i (≤ |P| + 1). Через F_P(i) и F'_P(i) обозначаются соответственно слабая и сильная функции неудачи для строки P: F_P(i) = sp_i−1(P) + 1, F'_P(i) = sp'_i−1(P) + 1 (значения sp_i(P) определены в Match21, а значения sp'_i(P) — в Match22). При этом дополнительно предполагается, что sp₀(P) = sp'₀(P) = 0. Найти F_P(i) и F'_P(i).

Match24°. Даны строки P, T и значения слабой функции неудач для строки P: F_P(i), i = 1, …, |P| + 1 (см. Match23). Найти все вхождения P в T, используя метод Кнута–Морриса–Пратта (метод КМП). Для этого использовать переменные p и t, хранящие текущие позиции строк P и T соответственно, инициализировав их значениями 1. Пока истинно условие |P| − p ≤ |T| − t, выполнять следующие действия:

• пока p ≤ |P| и P[p] = T[t], увеличивать на 1 переменные p и t;
• равенство p = |P| + 1 означает, что обнаружено очередное вхождение P в T (начиная с позиции t − |P|);
• если p = 1, то увеличить t на 1;
• положить переменную p равной значению слабой функции неудач F_P(p).

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Ускорение в методе КМП (по сравнению с наивным алгоритмом поиска) достигается за счет того, что изменение значения p (интерпретируемое как сдвиг образца P вправо относительно текста T) может выполняться на величину, большую 1. А именно, если несовпадение символов обнаружилось для P[i + 1] и T[t], то строка P сразу сдвигается вправо на i − sp_i(P) позиций (так что совмещаются символы P[sp_i(P) + 1] и T[t]). При этом гарантируется, что sp_i(P) начальных позиций в P совпадут с соответствующими позициями строки T, поэтому очередная проверка выполняется для символов P[sp_i(P) + 1] и T[t].

Match25°. Даны строки P, T и значения сильной функции неудач для строки P: F'_P(i), i = 1, …, |P| + 1 (см. Match23). Найти все вхождения P в T, используя модифицированный метод Кнута–Морриса–Пратта, отличающийся от исходного метода КМП (см. Match24) тем, что вместо функции F_P в нем используется сильная функция неудач F'_P. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Ускорение модифицированного метода КМП по сравнению с исходным состоит в том, что при сдвиге строки P вправо на i + sp'_i(P) позиций новый символ строки P, совмещенный с текущей позицией t строки T, будет заведомо отличаться от прежнего символа, для которого уже выявлено несовпадение.

Препроцессинг для метода Кнута–Морриса–Пратта

В данной подгруппе описываются два варианта быстрого препроцессинга образца P для метода Кнута–Морриса–Пратта (метода КМП). Первый вариант использует понятия основного препроцессинга (Z-блоки), второй является классическим препроцессингом метода КМП, использующим алгоритм рекурсивного спуска.

Match26°. Дано число n и набор значений Z_i(P), i = 2, …, n, для некоторой строки P длины n (см. Match9). Найти значения sp'_i(P) (см. Match22), используя соотношение sp'_i(P) = Z_j(P), где j > 1 — наименьший индекс, такой что i = j + Z_j(P) − 1 (данное соотношение справедливо для любого i > 1), а также соотношение sp'₁(P) = 0. Перебор j организовать в цикле с шагом −1 от n до 2, условные операторы не использовать. Вывести найденные значения sp'_i(P) для i = 1, …, n.

Match27°. Дано число n и набор значений Z_i(P), i = 2, …, n, для некоторой строки P длины n. Найти значения sp_i(P) (см. Match21), используя формулы для sp'_i(P), приведенные в Match26, а также соотношения sp₁(P) = 0, sp_n(P) = sp'_n(P), sp_i(P) = max{sp_i+1(P) − 1, sp'_i(P)}, i = 2, …, n − 1. Вывести найденные значения sp_i(P) для i = 1, …, n.

Match28°. Даны строки P и T. Используя модифицированный метод КМП (см. Match25), найти все вхождения P в T. Для вычисления сильной функции неудач F'_P использовать быстрый алгоритм основного препроцессинга (см. Match16) и формулы для sp'_i, приведенные в Match26. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также найденные в ходе основного препроцессинга значения Z_i(P), i = 2, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении основного препроцессинга).

Match29°. Даны строки P и T. Используя метод КМП (см. Match24), найти все вхождения P в T. Для вычисления слабой функции неудач F_P использовать быстрый алгоритм основного препроцессинга (см. Match16) и формулы для sp_i, приведенные в Match27. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также найденные в ходе основного препроцессинга значения Z_i(P), i = 2, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении основного препроцессинга).

Match30°. Дана строка P, число k (< |P|) и значения sp_i(P), i = 1, …, k. Найти значение sp_k+1(P), используя следующий алгоритм (препроцессинг по методу КМП). Положить x = P[k + 1] и v = sp_k(P). Пока символ P[v + 1] не совпадает с x и v > 0, выполнять переприсваивание v = sp_v(P) («рекурсивный спуск»). Если после завершения рекурсивного спуска символ P[v + 1] равен x, то значение sp_k+1(P) положить равным v + 1, в противном случае sp_k+1(P) = 0. Вывести значение sp_k+1(P) и количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. В алгоритме фактически требуется найти P' — наибольший собственный префикс подстроки P[1..k], который совпадает с суффиксом P[1..k] и за которым (в позиции |P'|+1) следует символ x. Первый шаг алгоритма почти очевиден: если x совпадает с символом P[sp_k(P) + 1], то sp_k+1(P) ≥ sp_k(P) + 1, и достаточно доказать, что оценка sp_k+1(P) > sp_k(P) + 1 никогда не выполняется (доказывается от противного). Отсутствие совпадения равносильно оценке sp_k+1(P) ≤ sp_k(P). Используя эту оценку, можно доказать, что искомая строка P' представляет собой наибольший собственный префикс P'' подстроки P[1..sp_k(P)], который совпадает с суффиксом P[1..k] и за которым (в позиции |P''| + 1) следует символ x. Сравнивая данное утверждение с первым предложением настоящего примечания, получаем алгоритм рекурсивного спуска.

Match31°. Дана строка P и число k (≤ |P|). Найти значения sp_i(P), i = 1, …, k, используя алгоритм препроцессинга по методу КМП, описанный в Match30 (в качестве начального шага алгоритма положить sp₁(P) = 0). Вывести полученные значения, а также количество сравнений символов, потребовавшееся для их нахождения.

Match32°. Дана строка P. Найти значения sp'_i(P), i = 1, …, |P| (см. Match22). Для этого предварительно определить значения sp_i(P), используя алгоритм препроцессинга по методу КМП (см. Match31). Для нахождения sp'_i(P) использовать следующий рекурсивный алгоритм (значения i перебираются от 1 до |P|): если sp_i(P) = 0, или i = |P|, или символы в позициях i + 1 и sp_i(P) + 1 не равны, то sp'_i(P) = sp_i(P), в противном случае sp'_i(P) = sp'_v(P), где v = sp_i(P). Вывести полученные значения sp'_i(P) и количество сравнений символов, потребовавшееся для их нахождения.

Match33°. Даны строки P и T. Используя метод КМП (см. Match24), найти все вхождения P в T. Для вычисления слабой функции неудач F_P использовать алгоритм препроцессинга по методу КМП (см. Match31). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения слабой функции неудач F_P(i), i = 1, …, |P| + 1, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Match34°. Даны строки P и T. Используя модифицированный метод КМП (см. Match25), найти все вхождения P в T. Для вычисления сильной функции неудач F'_P использовать алгоритм, приведенный в Match32. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения сильной функции неудач F'_P(i), i = 1, …, |P| + 1, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Метод реального времени

Метод поиска образца P в тексте T называется методом реального времени, если время проверки любой позиции в T не зависит от размера и свойств P. В частности, метод Кнута–Морриса–Пратта (как исходный, так и модифицированный) не является методом реального времени, так как при несовпадении символов T[t] и P[p] может потребоваться сравнение того же символа T[t] с несколькими другими символами образца P. В данной подгруппе заданий описывается вариант метода реального времени (этот метод называется также методом, основанным на использовании конечного автомата), в котором для каждой позиции текста T выполняется единственная проверка.

Match35°. Дана строка P и число k (≤ |P|). Через sp_i,x(P) (1 ≤ i ≤ |P|, x — некоторый символ) обозначается длина наибольшего собственного суффикса подстроки P[1..i], который совпадает с префиксом P и для которого выполняется дополнительное условие: символ в позиции sp_i,x(P) + 1 равен x. Если требуемые суффиксы отсутствуют, то sp_i,x(P) полагается равным 0 при P[1] = x и −1 в противном случае. Найти и вывести sp_i,x(P) для i = 1, …, |P|, используя в качестве x символ P[k].

Match36°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Кроме того, для каждой буквы x из Σ в алфавитном порядке («a», «b», «c», …) даны значения sp_i,x(P), i = 1, …, |P| (см. Match35). Найти все вхождения P в T, используя метод реального времени, имеющий следующие отличия от метода КМП (см. Match24):

• дополнительное действие при p = 1 не выполняется;
• значение p заменяется не на F_P(p) (равное sp_p−1(P) + 1), а на sp_p−1,x(P) + 2, где в качестве x указывается символ T[t], причем это действие выполняется только при наличии двух условий: p > 1 и t ≤ |T|;
• в конце каждой итерации внешнего цикла значение t увеличивается на 1.

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Ускорение метода реального времени по сравнению с методом КМП состоит в том, что при обнаружении несовпадения символов P[i + 1] и T[t] выполняется сдвиг строки P вправо на i − sp_i,T[t](P) − 1 позиций; при этом не требуется выполнять повторное сравнение символа строки P, совмещенного с прежней текущей позицией t строки T, и можно сразу переходить к сравнению следующей пары символов.

Match37°. Дана строка P и набор значений Z_i(P), i = 2, …, |P| (см. Match9). Кроме того, дано число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Найти значения sp_i,x(P) (см. Match35), модифицировав быстрый алгоритм нахождения sp'_i(P), описанный в Match26:

• вначале все значения sp_i,x(P) полагаются равными −1, а все значения sp'_i(P) равными 0;
• в цикле по j от |P| до 2 с шагом −1 значения sp_i,x(P) и sp'_i(P) полагаются равными Z_j(P), где i = j + Z_j(P) − 1, x = P[Z_j(P) + 1];
• если после завершения цикла значение sp_|P|,P[1](P) остается равным −1, то оно заменяется на 0;
• значения sp_i,x(P) в случае x = P[i + 1] определяются по формулам: sp_n−1,P[n](P) = sp'_n(P) − 1, где n = |P|; sp_i−1,P[i](P) = max{sp_i,P[i+1](P), sp'_i(P)} − 1, где i изменяется от |P| − 1 до 2 с шагом −1.

Вывести найденные значения sp_i,x(P), перебирая x из Σ в алфавитном порядке и для каждого x изменяя i от 1 до |P|.

Примечание. В первом цикле описанного алгоритма определяются значения sp_i,x(P) в случае x ≠ P[i + 1]. Рекуррентные формулы для sp_i,x(P) в случае x = P[i + 1] можно получить из соотношения sp_i−1,P[i](P) = sp_i(P) − 1, i = 2, …, |P|, с учетом алгоритма вычисления sp_i, приведенного в Match27.

Match38°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Используя метод реального времени (см. Match36), найти все вхождения P в T. Для вычисления sp_i,x(P) использовать быстрый алгоритм основного препроцессинга (см. Match16) и алгоритм, описанный в Match37. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения sp_i,x(P), i = 1, …, |P|, x = «a», и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при выполнении основного препроцессинга).

Правила сдвига по плохому символу и по хорошему суффиксу

Match39°. Дана строка P и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Через R_x(P) обозначается позиция крайнего правого вхождения символа x в строку P (если x не входит в P, то R_x(P) = 0). Выполняя однократный просмотр символов строки P и не используя условные операторы, найти R_x(P) для x из Σ и вывести найденные значения, перебирая x в алфавитном порядке.

Match40°. Дана строка P и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Через R_x,i(P), i = 1, …, |P|, обозначается позиция ближайшего вхождения символа x в строку P слева от позиции i (или 0, если требуемые вхождения отсутствуют). Организовав хранение значений R_x,i(P) в двумерном массиве и не используя условные операторы, найти R_x,i(P) для x из Σ и вывести найденные значения, перебирая x в алфавитном порядке и для каждого x изменяя i от 1 до |P|.

Match41°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Вычислить значения R_x(P) для x из Σ (см. Match39) и найти все вхождения P в T, используя посимвольное сравнение строк справа налево, а также правило сдвига по плохому символу. Для этого использовать переменную k, инициализировав ее значением |P|, и переменные p и t, хранящие текущие позиции строк P и T соответственно. Пока выполняется условие k ≤ |T|, выполнять следующие действия:

• положить p равной |P|, а t равной k;
• пока p > 0 и P[p] = T[t], уменьшать на 1 переменные p и t;
• равенство p = 0 означает, что обнаружено очередное вхождение P в T (начиная с позиции t + 1), в этом случае увеличить k на 1; в противном случае увеличить k на max{1, p − R_x(P)}, где в качестве x указывается T[t].

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения R_x(P) для x из Σ (перебирая x в алфавитном порядке) и количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Ускорение в методе, использующем правило сдвига по плохому символу (по сравнению с наивным алгоритмом поиска) достигается за счет того, что изменение значения k (интерпретируемое как сдвиг образца P вправо относительно текста T) может выполняться на величину, большую 1. А именно, если крайнее правое вхождение в P символа T[t] занимает позицию j, расположенную слева от текущей позиции P, то строка P сдвигается вправо таким образом, чтобы символ P[j] совместился с T[t]. Особенно эффективен такой сдвиг в случае, если T[t] не входит в строку-образец P (в этом случае j = 0, и начальная позиция строки P сразу совмещается с позицией t + 1 строки T).

Match42°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Вычислить значения R_x,i(P) для x из Σ (см. Match40) и найти все вхождения P в T, используя посимвольное сравнение строк справа налево и расширенное правило сдвига по плохому символу. Данное правило отличается от обычного правила сдвига по плохому символу (см. Match41) тем, что при увеличении переменной k вместо выражения p − R_T[t](P) используется выражение p − R_T[t],p(P). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения R_x,i(P), x = «a», i = 1, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Расширенное правило плохого символа более эффективно (по сравнению с обычным правилом) при обработке строк, содержащих большое количество повторяющихся символов.

Match43°. Дана строка P и число i (≤ |P|). Через L_i(P) обозначается наибольшая позиция в P, меньшая |P| и такая, что подстрока P[i..|P|] совпадает с суффиксом строки P[1..L_i(P)]. Если такой позиции нет, то L_i(P) = 0. Иначе говоря, L_i(P) определяет позицию правого конца крайней правой копии строки P[i..|P|], которая не является суффиксом P. Найти и вывести L_i(P).

Match44°. Дана строка P и число k (≤ |P|). Через L'_i(P), i = 2, …, |P|, обозначается наибольшая позиция в P, меньшая |P| и такая, что подстрока P[i..|P|] совпадает с суффиксом строки P[1..L'_i(P)], причем символ, предшествующий этому суффиксу, либо отсутствует, либо не равен P[i − 1]. Если такой позиции нет, то L'_i(P) = 0. В случае i = 1 по определению полагается L'₁(P) = 0. Таким образом, L'_i(P) ≤ L_i(P) (см. Match43). Найти и вывести L'_i(P) для i = 1, …, |P|.

Match45°. Дана строка P. Через s_i(P), i = 1, …, |P|, обозначается длина наибольшего суффикса подстроки P[i..|P|], который является собственным префиксом P. Если таких суффиксов не существует, то s_i(P) = 0. Найти и вывести s_i(P) для i = 1, …, |P|.

Match46°. Даны строки P и T, а также значения L_i(P) и s_i(P), i = 1, …, |P| (см. Match43 и Match45). Найти все вхождения P в T, используя посимвольное сравнение справа налево и слабое правило сдвига по хорошему суффиксу. Для этого использовать схему алгоритма, реализующего правило сдвига по плохому символу (см. Match41), изменив его заключительное действие следующим образом:

• если p = 0, т. е. обнаружено очередное вхождение P в T (начиная с позиции t + 1), то увеличить k на |P| − s₂(P); в противном случае, если p = |P|, то увеличить k на 1, а если p < |P|, то в случае L_p+1(P) > 0 увеличить k на |P| − L_p+1(P), а в случае L_p+1(P) = 0 увеличить k на |P| − s_p+1(P).

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Приведем словесное описание слабого правила сдвига по хорошему суффиксу: если обнаружена подстрока T' из T, совпадающая с суффиксом P и такая, что символы слева от этих подстрок не совпадают, то в P ищется крайняя правая подстрока P', совпадающая с T' и не являющаяся суффиксом P, после чего P сдвигается вправо так, чтобы подстрока P' строки P совместилась с подстрокой T' строки T. Если требуемая подстрока P' отсутствует (ситуация L_p+1(P) = 0), то выполняется наименьший сдвиг P вправо, при котором префикс сдвинутой строки P совпадет с некоторым суффиксом подстроки T' в T (если такого сдвига не существует, то P сдвигается на |P| позиций вправо). При обнаружении вхождения P выполняется наименьший сдвиг вправо, при котором собственный префикс сдвинутой строки P совпадет с некоторым суффиксом найденного вхождения P в T (если такого сдвига не существует, то P сдвигается на |P| позиций вправо).

Match47°. Даны строки P и T, а также значения L'_i(P) и s_i(P), i = 1, …, |P| (см. Match44 и Match45). Найти все вхождения P в T, используя посимвольное сравнение справа налево и сильное правило сдвига по хорошему суффиксу, отличающееся от слабого правила (см. Match46) тем, что при увеличении переменной k вместо значений L_p+1(P) используются значения L'_p+1(P). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Примечание. Сильное правило сдвига по хорошему суффиксу отличается от слабого тем, что если обнаружена подстрока T' из T, совпадающая с суффиксом P, и такая, что символы слева от этих подстрок не совпадают, то в P ищется крайняя правая подстрока P', не только совпадающая с T', но и обладающая дополнительным свойством: символ слева от P' не равен символу слева от суффикса строки P, равного T'.

Match48°. Дана строка P и число i (< |P|). Через N_i(P), i = 1, …, |P| − 1, обозначается длина наибольшего суффикса строки P[1..i], который также является суффиксом полной строки P. Если такого суффикса нет, то N_i(P) = 0. Найти и вывести N_i(P).

Match49°. Дана строка P. Реализовать следующий алгоритм вычисления значений N_i(P) (см. Match48):

• инвертировать строку P, получив в результате строку P';
• используя быстрый алгоритм основного препроцессинга для строки P' (см. Match16), найти значения Z_j(P'), j = 2, …, |P|;
• положить значение N_i(P) равным Z_|P|−i+1(P'), i = 1, …, |P| − 1.

Вывести найденные значения N_i(P) для i = 1, …, |P| − 1. Вывести также количество сравнений символов, потребовавшееся при выполнении основного препроцессинга.

Match50°. Дано число n и набор значений N_i(P), i = 1, …, n − 1, для некоторой строки P длины n (см. Match48). Найти значения L'_i(P) для i = 1, …, n (см. Match44), используя соотношение L'_i(P) = j, где j < n — наибольший индекс, такой что i = n − N_j(P) + 1 (если требуемые индексы j отсутствуют, то L'_i(P) = 0). Перебор j организовать в цикле от 1 до n − 1 с шагом 1, условные операторы не использовать. Вывести найденные значения L'_i(P).

Match51°. Дано число n и набор значений N_i(P), i = 1, …, n − 1, для некоторой строки P длины n (см. Match48). Найти значения L_i(P) для i = 1, …, n (см. Match43), используя формулы для L'_i(P), приведенные в Match50, а также соотношения L₁(P) = 0, L_i(P) = max{L_i−1(P), L'_i(P)}, i = 2, …, n. Вывести найденные значения L_i(P).

Match52°. Дано число n и набор значений N_i(P), i = 1, …, n − 1, для некоторой строки P длины n (см. Match48). Найти значения s_i(P) для i = 1, …, n (см. Match45), используя соотношение s_i(P) = j, где j ≤ n − i + 1 — наибольший индекс, такой что N_j(P) = j (если требуемые индексы j отсутствуют, то s_i(P) = 0). Алгоритм не должен содержать вложенных циклов (ср. с Match51). Вывести найденные значения s_i(P).

Метод Бойера–Мура

Метод Бойера–Мура представляет собой комбинацию правил сдвига по плохому символу и сдвига по хорошему суффиксу и является, наряду с методом Кнута–Морриса–Пратта, одним из наиболее известных быстрых алгоритмов поиска подстрок. Особенностью данного метода является то, что при его применении для поиска вхождений P в T обычно проверяется менее, чем |P| + |T| символов (так называемый поиск за сублинейное время).

Match53°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны значения R_x(P) для x из Σ (см. Match39, символы x перебираются в алфавитном порядке) и значения L_i(P) и s_i(P), i = 1, …, |P| (см. Match43 и Match45). Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий правило сдвига по плохому символу (см. Match41) и слабое правило сдвига по хорошему суффиксу (см. Match46). Для этого использовать схему алгоритма, применяющего слабое правило сдвига по хорошему суффиксу, дополнив его заключительное действие следующим образом:

• если p > 0, т. е. вхождение P в T не обнаружено, то увеличить k на max{s, p − R_T[t](P)}, где s — величина сдвига, вычисленная по слабому правилу хорошего суффикса.

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match54°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны значения R_x(P) для x из Σ (см. Match39, символы x перебираются в алфавитном порядке) и значения L'_i(P) и s_i(P), i = 1, …, |P| (см. Match44 и Match45). Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий правило сдвига по плохому символу (см. Match41) и сильное правило сдвига по хорошему суффиксу (см. Match47). Для этого использовать схему алгоритма, применяющего сильное правило сдвига по хорошему суффиксу, дополнив его заключительное действие следующим образом:

• если p > 0, т. е. вхождение P в T не обнаружено, то увеличить k на max{s, p − R_T[t](P)}, где s — величина сдвига, вычисленная по сильному правилу хорошего суффикса.

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match55°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны значения R_x,i(P) для x из Σ (см. Match40, символы x перебираются в алфавитном порядке, для каждого x значение i меняется от 1 до |P|) и значения L_i(P) и s_i(P), i = 1, …, |P| (см. Match43 и Match45). Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий расширенное правило сдвига по плохому символу (см. Match42) и слабое правило сдвига по хорошему суффиксу (см. Match46). Для этого использовать схему алгоритма, применяющего слабое правило сдвига по хорошему суффиксу, дополнив его заключительное действие следующим образом:

• если p > 0, т. е. вхождение P в T не обнаружено, то увеличить k на max{s, p − R_T[t],p(P)}, где s — величина сдвига, вычисленная по слабому правилу хорошего суффикса.

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match56°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны значения R_x,i(P) для x из Σ (см. Match40, символы x перебираются в алфавитном порядке, для каждого x значение i меняется от 1 до |P|) и значения L'_i(P) и s_i(P), i = 1, …, |P| (см. Match44 и Match45). Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий расширенное правило сдвига по плохому символу (см. Match42) и сильное правило сдвига по хорошему суффиксу (см. Match47). Для этого использовать схему алгоритма, применяющего сильное правило сдвига по хорошему суффиксу, дополнив его заключительное действие следующим образом:

• если p > 0, т. е. вхождение P в T не обнаружено, то увеличить k на max{s, p − R_T[t],p(P)}, где s — величина сдвига, вычисленная по сильному правилу хорошего суффикса.

Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также количество сравнений символов, потребовавшееся при выполнении алгоритма.

Match57°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий правило сдвига по плохому символу и слабое правило сдвига по хорошему суффиксу (см. Match53). Для вычисления значений L_i(P) и s_i(P) использовать быстрый алгоритм препроцессинга, описанный в Match49–Match52). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения R_x(P), перебирая x из Σ в алфавитном порядке, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Match58°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий правило сдвига по плохому символу и сильное правило сдвига по хорошему суффиксу (см. Match54). Для вычисления значений L'_i(P) и s_i(P) использовать быстрый алгоритм препроцессинга, описанный в Match49, Match50, Match52). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения s_i(P), i = 1, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Match59°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий расширенное правило сдвига по плохому символу и слабое правило сдвига по хорошему суффиксу (см. Match55). Для вычисления значений L_i(P) и s_i(P) использовать быстрый алгоритм препроцессинга, описанный в Match49–Match52). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения L_i(P), i = 1, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Match60°. Даны строки P, T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Найти все вхождения P в T, используя вариант метода Бойера–Мура, совместно применяющий расширенное правило сдвига по плохому символу и сильное правило сдвига по хорошему суффиксу (см. Match56). Для вычисления значений L'_i(P) и s_i(P) использовать быстрый алгоритм препроцессинга, описанный в Match49, Match50, Match52). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также значения L'_i(P), i = 1, …, |P|, и количество сравнений символов, потребовавшееся при выполнении алгоритма (в том числе и при проведении препроцессинга).

Битовый метод поиска точных и неточных вхождений

В данной подгруппе заданий рассматривается битовый метод поиска (метод Shift-And) — один из получисленных методов поиска, основанный не на сравнении символов, а на битовых и арифметических операциях. Рассматривается также его модификация, позволяющая выполнять поиск неточных вхождений.

Match61°. Даны строки P, T (|P| < 32) и число j (0 ≤ j ≤ |T|). Через M(P, T) обозначается битовая матрица размера |P| × (|T| + 1), элементы которой M_i,j(P, T), i = 1, …, |P|, j = 0, …, |T|, равны 1, если первые i символов P совпадают с i символами T, кончающимися на позиции j (т. е. P[1..i] = T[j−i+1..j]), и равны 0 в противном случае. Через M_j(P, T) обозначается j-й столбец матрицы M(P, T). Для данных P и T сформировать столбец M_j(P, T) и получить его числовое представление, т. е. представление в виде целого числа, двоичная запись которого (дополненная слева нулями до |P| разрядов) совпадает с элементами вектора M_j(P, T), перебираемыми в порядке возрастания индексов (например, вектор-столбцу (0, 1, 1)^T соответствует числовое представление 3). Вывести элементы столбца M_j(P, T) и соответствующее ему числовое представление.

Примечание. Элементы матрицы M(P, T), равные 1 в строчке i, показывают все позиции в T, где заканчивается копия подстроки P[1..i], поэтому по последней строчке матрицы M можно определить завершающие позиции всех вхождений P в T.

Match62°. Дана строка P (|P| < 32) и число k (≤ |P|). Через U(x, P), где x — некоторый символ, обозначается битовый вектор длины |P|, для которого U_i(x, P) = 1, если P[i] = x, и U_i(x, P) = 0 в противном случае. Для данной строки P найти вектор U(P[k], P) и вывести его элементы, а также соответствующее ему числовое представление (определение числового представления дано в Match61).

Match63°. Дана строка P (|P| < 32) и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Для каждого символа x из Σ найти числовое представление вектора U(x, P) (см. Match62) и вывести эти представления, перебирая x в алфавитном порядке. Для хранения числовых представлений векторов использовать массив. Сформировать все числовые представления за однократный просмотр строки, вложенные циклы не использовать.

Match64°. Даны числа v и p; p = 2ⁿ для некоторого n > 0, v является числовым представлением некоторого вектора V длины n (определение числового представления дано в Match61). Через RShift(V) обозначается вектор V', полученный из вектора V сдвигом всех его элементов на 1 позицию в направлении увеличения индексов, причем первый элемент вектора V' полагается равным 1, а последний элемент вектора V теряется. Используя арифметические и побитовые операции над целыми числами и не применяя циклы, найти числовые представления векторов RShift(V) и RShift(RShift(V)). Оформить вычисление числового представления RShift(V) в виде вспомогательной функции с параметрами v и p.

Match65°. Дана строка T и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны характеристики некоторой строки P: ее длина n и числовые представления векторов U(x, P) для всех x из Σ (см. Match62, символы x перебираются в алфавитном порядке). Найти столбцы матрицы M(P, T) (см. Match61), используя следующий алгоритм:

• столбец M₀ является нулевым;
• для любого j > 0 столбец M_j вычисляется по формуле M_j = RShift(M_j−1) and U(T[j], P) (операция RShift описана в Match64).

Все вычисления проводить над числовыми представлениями векторов; при нахождении матрицы M хранить только два ее столбца: вычисляемый и найденный на предыдущем шаге. В процессе вычисления столбцов M_j, j = 1, …, |T|, выводить их числовые представления.

Примечание. Формула отражает тот факт, что i-й элемент столбца M_j будет равен 1 тогда и только тогда, когда подстрока P[1..i − 1] совпадет с подстрокой T той же длины, оканчивающейся в позиции j − 1 (в этом случае i-й элемент вектора RShift(M_j−1) будет равен 1), и, кроме того, символ P[i] совпадет с T[j] (в этом случае i-й элемент вектора U(T[j], P) также будет равен 1).

Match66°. Даны строки P, T (|P| < 32) и число m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Известно, что имеется хотя бы одно вхождение образца P в текст T. Найти все вхождения P в T, используя битовый метод поиска. Для этого сформировать векторы U(x, P) для всех x из Σ (см. Match63), после чего организовать последовательное вычисление столбцов матрицы M(P, T) (см. Match65). Вхождения P в T определять, анализируя последние элементы столбцов M_j(P, T) (см. примечание к Match61; для числовых представлений столбцов достаточно проанализировать их четность). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), а также числовые представления U(x, P), перебирая x из Σ в алфавитном порядке, и числовое представление столбцов M_j(P, T), соответствующих конечным позициям j найденных вхождений (числовые представления всех этих столбцов будут одинаковыми).

Match67°. Даны строки P, T (|P| < 32) и числа k (k ≤ 5) и j (0 ≤ j ≤ |T|). Через M^k(P, T), k ≥ 0, обозначается битовая матрица размера |P| × (|T|+1), элементы которой M^k_i,j(P, T), i = 1, …, |P|, j = 0, …, |T|, равны 1, если не менее i − k из первых i символов P совпадают с соответствующими символами из i символов T, кончающихся на позиции j (т. е. P[1..i] отличается от T[j − i + 1..j] не более чем в k позициях). В противном случае M^k_i,j(P, T) = 0. Через M^k_j(P, T) обозначается j-й столбец матрицы M^k(P, T). Для данных P и T сформировать столбец M^k_j и получить его числовое представление (определение числового представления приведено в Match61). Вывести элементы столбца M^k_j и соответствующее ему числовое представление.

Примечание. Единичные элементы строки матрицы M^k(P, T) с номером |P| соответствуют завершающим позициям всех неточных вхождений P в T с не более чем k несовпадающими символами (называемых также вхождениями с не более чем k ошибками).

Match68°. Дана строка T и числа k (≤ 5) и m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Также даны характеристики некоторой строки P: ее длина n и числовые представления векторов U(x, P) для всех x из Σ (см. Match62, символы x перебираются в алфавитном порядке). Для данного k найти столбцы матрицы M^k(P, T) (см. Match67), используя следующий алгоритм:

• при фиксированном j = 0, …, |T| последовательно вычисляются M^q_j для q = 0, …, k;
• для любого q столбец M^q₀ является нулевым;
• столбец M⁰_j вычисляется по формуле M⁰_j = RShift(M⁰_j−1) and U(T[j], P) (операция RShift описана в Match64);
• для j > 0 столбец M^q_j вычисляется по формуле M^q_j = RShift(M^q−1_j−1) or (RShift(M^q_j−1) and U(T[j], P)).

Все вычисления проводить над числовыми представлениями векторов; при нахождении матриц M^q хранить только два набора их столбцов: вычисляемый M^q_j и найденный на предыдущем шаге M^q_j−1. В процессе вычисления столбцов M^k_j, j = 1, …, |T|, выводить их числовые представления.

Примечание. Формула для вычисления M^q_j при положительных q и j отражает тот факт, что i первых символов строки P и i символов строки T, оканчивающихся в позиции j, будут иметь не более q несовпадений в том и только том случае, если i − 1 первых символов строки P и i − 1 символов строки T, оканчивающихся в позиции j − 1, будут иметь не более q − 1 несовпадений (эту ситуацию проверяет операнд RShift(M^q−1_j−1) либо i − 1 первых символов строки P и i − 1 символов строки T, оканчивающихся в позиции j − 1, будут иметь не более q несовпадений и при этом пара символов P[i] и T[j] будет совпадать (эту ситуацию проверяет операнд RShift(M^q_j−1) and U(T[j], P)).

Match69°. Даны строки P, T (|P| < 32) и числа k (≤ 5) и m (< 10); алфавит Σ представляет собой m первых строчных латинских букв. Известно, что имеется хотя бы одно вхождение образца P в текст T, содержащее не более k несовпадений. Найти все такие вхождения P в T, используя битовый метод неточного поиска. Для этого сформировать векторы U(x, P) для всех x из Σ (см. Match62), после чего организовать последовательное вычисление столбцов матрицы M^k(P, T) (см. Match68). Неточные вхождения P в T определять, анализируя последние элементы столбцов M^k_j (см. примечание к Match67; для числовых представлений столбцов достаточно проанализировать их четность). Для каждого найденного неточного вхождения P в T выводить его начальную позицию и числовое представление M^k_j, где j — номер конечной позиции данного вхождения. Вхождения перебирать в порядке возрастания их начальных позиций.

Метод дактилограмм Карпа–Рабина

В данной подгруппе рассматривается еще один из получисленных алгоритмов поиска: метод дактилограмм Карпа–Рабина. Хотя данный метод допускает так называемые ложные совпадения, доказано, что при надлежащем выборе числа q, используемого в методе, вероятность появления ложных совпадений можно сделать достаточно малой.

Match70°. Дана строка S, состоящая из символов «0» и «1» (|S| < 32). Через H(S) обозначается число, строковое представление которого в двоичной системе счисления совпадает со строкой S: H(S) = Σ_i=1^|S| 2^|S|−i·d(S[i]), где d(«0») = 0, d(«1») = 1. Найти Н(S), используя схему Горнера:

H(S) = (…(((d(S[1])·2 + d(S[2]))·2 + d(S[3]))·2 + d(S[4]))…)·2 + d(S[|S|]).

Match71°. Дана строка T, состоящая из символов «0» и «1», число n (< min{|T|, 31}) и значение H(T[1..n]) (см. Match70). Найти и вывести значения H(Tⁿ_k), k = 2, …, |T| − n + 1, где Tⁿ_k = T[k..k + n − 1] — подстрока строки T, имеющая длину n и начинающаяся в позиции k. Для вычисления H(Tⁿ_k) использовать рекуррентную формулу: H(Tⁿ_k) = H(Tⁿ_k−1)·2 − d(T[k − 1])·2ⁿ + d(T[k + n − 1]).

Match72°. Даны строки P и T, состоящие из символов «0» и «1», |P| < 31. Найти все вхождения P в T, сравнивая значения H(P) и H(Tⁿ_k), k = 1, …, |T| − n + 1, где n = |P| (определение H(S) дано в Match70, обозначение Tⁿ_k и быстрый алгоритм вычисления H(Tⁿ_k) приведены в Match71). Строка P входит в T, начиная с позиции k, тогда и только тогда, когда H(P) = H(Tⁿ_k). Вывести H(P), H(Tⁿ₁) и начальные позиции всех найденных вхождений P в T (в порядке возрастания), после чего дополнительно вывести H(Tⁿ_|T|−n+1).

Match73°. Дана строка S, состоящая из символов «0» и «1», и число q. Через H_q(S) обозначается число, равное Н(S) mod q, где число H(S) определено в Match70, а «mod» обозначает операцию взятия остатка от деления нацело. Значение H_q(S) лежит в диапазоне от 0 до q − 1 и называется дактилограммой строки S. Найти Н_q(S), используя вариант схемы Горнера, в котором ни один результат умножения не превосходит 2·q: H_q(S) = ((…(((d(S[1])·2 mod q + d(S[2]))·2 mod q + d(S[3]))·2 mod q + d(S[4]))…)·2 mod q + d(S[|S|])) mod q. Вывести промежуточные результаты вычислений, полученные перед каждой операцией умножения на 2, а также найденное значение H_q(S).

Match74°. Дана строка T, состоящая из символов «0» и «1», числа n (< |T|) и q, а также значение H_q(T[1..n]) (см. Match73). Найти и вывести значения H_q(Tⁿ_k), k = 2, …, |T| − n + 1 (обозначение Tⁿ_k описано в Match71). Для вычисления H_q(Tⁿ_k) использовать рекуррентную формулу: H_q(Tⁿ_k) = (H_q(Tⁿ_k−1)·2 − d(T[k − 1])·(2ⁿ mod q) + d(T[k + n − 1]) + q) mod q. Для вычисления 2ⁿ mod q использовать схему, в которой промежуточные результаты не превосходят 2·q: 2ⁿ mod q = 2·(…(2·(2·2 mod q) mod q)…) mod q.

Match75°. Даны строки P и T, состоящие из символов «0» и «1», и число q. Найти все вхождения P в T используя метод дактилограмм Карпа–Рабина. Для этого найти и сравнить значения H_q(P) и H_q(Tⁿ_k), k = 1, …, |T| − n + 1, где n = |P| (определение H_q(S) дано в Match73, обозначение Tⁿ_k — в Match71, быстрый алгоритм вычисления H_q(Tⁿ_k) — в Match74). Если H_q(P) = H_q(Tⁿ_k), то строка P, возможно, входит в T, начиная с позиции k; в этом случае надо провести дополнительное сравнение символов в порядке слева направо до первого несовпадения символов (случай ложного совпадения) или до успешного подтверждения обнаруженного вхождения. Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), после чего дополнительно вывести общее количество выполненных сравнений символов и количество выявленных ложных совпадений.

Match76°. Дана строка S (|S| < 10) и число m (1 < m < 10); алфавит представляет собой m первых цифр («0», «1», «2», …). Через H^m(S) обозначается число, строковое представление которого в m-ичной системе счисления совпадает со строкой S: H^m(S) = Σ_i=1^|S| m^|S|-i·d(S[i]), где d(«0») = 0, d(«1») = 1, d(«2») = 2, … . Найти Н^m(S), используя схему Горнера:

H(S) = (…(((d(S[1])·m + d(S[2]))·m + d(S[3]))·m + d(S[4]))…)·m + d(S[|S|]).

Match77°. Дана строка S и числа q и m (1 < m ≤ 10); алфавит представляет собой m первых цифр. Через H^m_q(S) обозначается число, равное Н^m(S) mod q, где H^m(S) определено в Match76, а «mod» обозначает операцию взятия остатка от деления нацело. Найти Н^m_q(S), используя вариант схемы Горнера, в котором ни один результат умножения не превосходит m·(q + m − 2): H^m_q(S) = ((…(((d(S[1])·m mod q + d(S[2]))·m mod q + d(S[3]))·m mod q + d(S[4]))…)·m mod q + d(S[|S|])) mod q. Вывести промежуточные результаты вычислений, полученные перед каждой операцией умножения на m, а также найденное значение H^m_q(S).

Match78°. Дана строка T, числа n (< |T|), q и m (1 < m ≤ 10); алфавит представляет собой m первых цифр. Кроме того, дано значение H^m_q(T[1..n]) (см. Match77). Найти и вывести значения H^m_q(Tⁿ_k), k = 2, …, |T| − n + 1 (обозначение Tⁿ_k определено в Match71). Для вычисления H^m_q(Tⁿ_k) использовать рекуррентную формулу: H^m_q(Tⁿ_k) = (H^m_q(Tⁿ_k−1)·m − d(T[k − 1])·(mⁿ mod q) + d(T[k + n − 1]) + (m − 1)·q) mod q. Для вычисления mⁿ mod q использовать схему, в которой промежуточные результаты не превосходят m·q: mⁿ mod q = m·(…((m·(m mod q) mod q))…) mod q.

Match79°. Даны строки P, T и числа q и m (1 < m ≤ 10); алфавит представляет собой m первых цифр. Найти все вхождения P в T используя вариант метода дактилограмм Карпа–Рабина (см. Match75), в котором применяются дактилограммы H^m_q(S) (см. Match77–Match78). Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), после чего дополнительно вывести общее количество сравнений символов и количество выявленных ложных совпадений.

Match80°. Даны строки P, T и числа q и m (1 < m ≤ 26); алфавит представляет собой m первых строчных латинских букв. Найти все вхождения P в T используя вариант метода дактилограмм Карпа–Рабина (см. Match75), в котором применяются дактилограммы H^m_q(S) (см. Match77–Match78), причем d(«a») = 0, d(«b») = 1, d(«c») = 2, …, d(«k») = 10, … . Вывести начальные позиции всех найденных вхождений P в T (в порядке возрастания), после чего дополнительно вывести общее количество сравнений символов и количество выявленных ложных совпадений.

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024