((((((((a?b)?a)?c)?a)?b)?a)?d)?
Очевидно, это регулярное выражение, под которое подпадают все суффиксы строки abacabad, и только они. Понятно, как построить аналогичное выражение для произвольной строки, размер выражения будет примерно 4·n, где n — длина строки.
Вопрос: есть ли обработчики регулярных выражений, которые
а) осилят перевести это (можно неявно) в суффиксный автомат
б) и сделают это за полиномиальное время
в) и сделают это за линейное время?
Очевидно, это регулярное выражение, под которое подпадают все суффиксы строки abacabad, и только они. Понятно, как построить аналогичное выражение для произвольной строки, размер выражения будет примерно 4·n, где n — длина строки.
Вопрос: есть ли обработчики регулярных выражений, которые
а) осилят перевести это (можно неявно) в суффиксный автомат
б) и сделают это за полиномиальное время
в) и сделают это за линейное время?
(((((((((a? b)? a)? c)? a)? b)? a)? d)?
Obviously, this is a regular expression that matches all suffixes of the abacabad string, and only they. It is clear how to build a similar expression for an arbitrary string, the size of the expression will be about 4 · n, where n is the length of the string.
Question: are there regular expression handlers that
a) they will be able to translate this (you can implicitly) into a suffix machine
b) and do it in polynomial time
c) and do it in linear time?
Obviously, this is a regular expression that matches all suffixes of the abacabad string, and only they. It is clear how to build a similar expression for an arbitrary string, the size of the expression will be about 4 · n, where n is the length of the string.
Question: are there regular expression handlers that
a) they will be able to translate this (you can implicitly) into a suffix machine
b) and do it in polynomial time
c) and do it in linear time?
У записи 1 лайков,
0 репостов.
0 репостов.
Эту запись оставил(а) на своей стене Олег Давыдов
