В новом языке программирования все программы записываются в одну строчку, а используемых символов всего три: ’/’ , ’*’ и ’.’. При этом комментарии имеют вид "/*S*/", где S не содержит подстроки "*/", или вид "/*S", если последовательность "*/" не встречается до конца программы. Комментарии не могут пересекаться и определяются при просмотре символов текста программы, начиная с самого первого. К сожалению, программам разрешается изменять свой собственный текст, поэтому нахождение комментариев становится непростым делом. Напишите программу, которая определяет, является ли данный символ в данный момент времени частью комментария в программе на новом языке программирования.
Ограничения: 1 ≤ |S| ≤ 100'000, число запросов n (1 ≤ n ≤ 100'000). В следующих n строках находятся запросы двух типов. Если нужно изменить символ в программе, то в строке записано число 1, позиция символа от 1 до |S| и новое значение символа в этой позиции. Если нужно узнать, является ли символ комментарием, то в строке записано число 2 и позиция символа от 1 до |S|.
Здравствуйте, Serge, Вы писали:
S>Есть такая задача с одного из конкурсов.
Если нет ограничений по времени, то и задачи-то нет — парси каждый раз с начала и смотри коммент это или нет.
Помню ещё в W95-W98 делал подсветку синтаксиса для C подобного языка — даже на тех процессорах и той памяти всё работало комфортно при тупом парсинге с начала при каждом вводе символа (но лимит тогда был 10000 байт кода).
Здравствуйте, VVV, Вы писали:
VVV>Здравствуйте, Serge, Вы писали:
S>>Есть такая задача с одного из конкурсов.
VVV>Если нет ограничений по времени, то и задачи-то нет — парси каждый раз с начала и смотри коммент это или нет.
Здравствуйте, Serge, Вы писали:
S>Есть такая задача с одного из конкурсов.
S>В новом языке программирования все программы записываются в одну строчку, а используемых символов всего три: ’/’ , ’*’ и ’.’. При этом комментарии имеют вид "/*S*/", где S не содержит подстроки "*/", или вид "/*S", если последовательность "*/" не встречается до конца программы. Комментарии не могут пересекаться и определяются при просмотре символов текста программы, начиная с самого первого. К сожалению, программам разрешается изменять свой собственный текст, поэтому нахождение комментариев становится непростым делом. Напишите программу, которая определяет, является ли данный символ в данный момент времени частью комментария в программе на новом языке программирования.
S>Ограничения: 1 ≤ |S| ≤ 100'000, число запросов n (1 ≤ n ≤ 100'000). В следующих n строках находятся запросы двух типов. Если нужно изменить символ в программе, то в строке записано число 1, позиция символа от 1 до |S| и новое значение символа в этой позиции. Если нужно узнать, является ли символ комментарием, то в строке записано число 2 и позиция символа от 1 до |S|.
Как это делается в редакторах?
Разбор произвольного языка программирования на лексемы (комментарии, числа, идентификаторы,...) можно рассматривать как как работу машинки конечного числа состояний, на вход которой подаются символы программы. При вводе нового символа может измениться подсветка только символов стоящих ниже по тексту. Пользователя обычно интересует подсветка символов в окрестности той части текста, которая только что изменилась (пользовать смотрит на текст, который редактирует +/- размер экрана).
Поэтому очевидное решение:
Храним массив целых чисел, длинна которого соответствует длине текста +1. В массиве хранится номер состояния в котором находилась машинка перед поступлением на вход соответствующего символа текста. + Храним число: до какого символа построенный нами массив состояний валиден.
Если пользователь изменил символ — это это только укорачивает длину валидного участка вектора состояний.
Если поступил запрос на состояние на i-й позиции — тогда запускаем машинку от последнего валидного состояния — до запрошенного символа, удлиняя валидную часть вектора состояний до i.
Оптимизация: если исправление символа не повлияло на состояние следующего символа — то вектор состояний можно не сбрасывать.
Однако, в случае злых экзаменаторов, данный подход может не дать требуемой производительности (100000 запросов в к концу файла, каждый раз после исправления первого символа файла).
Что можно сделать в данном случае?
Воспользуемся тем, что у нас разрешена только операция замены символа (но не вставки/удаления).
Разобьем текст на (вложенные) отрезки по степеням двойки.
Для каждого отрезка будем хранить массив преобразования состояния (т.е. для каждого состояния (машинки состояний) перед началом отрезка — будем ставить в соответствие ее состояние в конце отрезка).
Таким образом, операция исправления символа затронет только O(log2(|S|)) отрезков.
Операция запроса состояния, также, потребует O(log2(i)) обращений к отрезкам.
Должны уложиться.