tugunchinov/mipt-flat-2020-practice1

Практикум №1

Регулярные выражения

Аргументами являются строка в алфавите {a, b, c, 1 , ., +, *}, а также некоторые дополнительные параметры. Первым компонентом является регулярное выражение \alpha в обратной польской записи, задающее язык L.

Задача 19.

Даны \alpha и буква x. Найти максимальное k, такое что в L есть слова, заканчивающиеся на x^k.

Решение.

Создадим стек, в котором будет храниться структура, содержащая информацию

1. ответ на задачу для текущего выражения;
2. максимальную длину слова, состоящего только из входного символа.

Начнем читать строку с начала. Если очередной прочитанный символ

1. пустое слово 1: максимальное k, очевидно, 0;
2. символ алфавита: если символ совпадает с входным, то k = 1, иначе k = 0;
3. плюс +: т. к. при составлении регулярного выражения можно выбирать одно из двух, то k = max(lhs.max_k, rhs.max_k);
4. точка .: т. к. слово будет заканчиваться на выражение, задаваемое правым операндом, то
   1. если правое выражение содержит x^k, то k = max(lhs.max_k + rhs.max_x_len, rhs.max_k);
   2. иначе слово будет заканчиваться на то, на что заканчивается rhs, поэтому k = rhs.max_k;
5. звезда Клини *: если в языке есть слово, состоящее только из входного слова любой ненулевой длины, то k = INF, иначе k не меняется.

Время работы

Т. к. цикл совершает n итераций, где n - длина входного выражения, а на каждой итерации совершается O(1) операций, то время работы алгоритма - O(n).

mipt-flat-2020-practice1's Issues

Комментарии

Хранить длину слова только из x

Переименовать regex1, regex2 => lhs, rhs