Аргументами являются строка в алфавите {a, b, c, 1 , ., +, *}
, а также некоторые дополнительные параметры. Первым компонентом
является регулярное выражение \alpha
в обратной польской записи, задающее язык L
.
Даны \alpha
и буква x
. Найти максимальное k
, такое что в L
есть слова, заканчивающиеся на x^k
.
Создадим стек, в котором будет храниться структура, содержащая информацию
- ответ на задачу для текущего выражения;
- максимальную длину слова, состоящего только из входного символа.
Начнем читать строку с начала. Если очередной прочитанный символ
- пустое слово
1
: максимальноеk
, очевидно,0
; - символ алфавита: если символ совпадает с входным, то
k = 1
, иначеk = 0
; - плюс
+
: т. к. при составлении регулярного выражения можно выбирать одно из двух, тоk = max(lhs.max_k, rhs.max_k)
; - точка
.
: т. к. слово будет заканчиваться на выражение, задаваемое правым операндом, то- если правое выражение содержит
x^k
, тоk = max(lhs.max_k + rhs.max_x_len, rhs.max_k)
; - иначе слово будет заканчиваться на то, на что заканчивается
rhs
, поэтомуk = rhs.max_k
;
- если правое выражение содержит
- звезда Клини
*
: если в языке есть слово, состоящее только из входного слова любой ненулевой длины, тоk = INF
, иначеk
не меняется.
Т. к. цикл совершает n
итераций, где n
- длина входного выражения,
а на каждой итерации совершается O(1)
операций, то время работы
алгоритма - O(n)
.