Комментарии
От: Serge  
Дата: 24.08.20 09:28
Оценка:
Есть такая задача с одного из конкурсов.

В новом языке программирования все программы записываются в одну строчку, а используемых символов всего три: ’/’ , ’*’ и ’.’. При этом комментарии имеют вид "/*S*/", где S не содержит подстроки "*/", или вид "/*S", если последовательность "*/" не встречается до конца программы. Комментарии не могут пересекаться и определяются при просмотре символов текста программы, начиная с самого первого. К сожалению, программам разрешается изменять свой собственный текст, поэтому нахождение комментариев становится непростым делом. Напишите программу, которая определяет, является ли данный символ в данный момент времени частью комментария в программе на новом языке программирования.

Ограничения: 1 ≤ |S| ≤ 100'000, число запросов n (1 ≤ n ≤ 100'000). В следующих n строках находятся запросы двух типов. Если нужно изменить символ в программе, то в строке записано число 1, позиция символа от 1 до |S| и новое значение символа в этой позиции. Если нужно узнать, является ли символ комментарием, то в строке записано число 2 и позиция символа от 1 до |S|.
Re: Комментарии
От: VVV Россия  
Дата: 24.08.20 22:39
Оценка: +1
Здравствуйте, Serge, Вы писали:

S>Есть такая задача с одного из конкурсов.


Если нет ограничений по времени, то и задачи-то нет — парси каждый раз с начала и смотри коммент это или нет.

Помню ещё в W95-W98 делал подсветку синтаксиса для C подобного языка — даже на тех процессорах и той памяти всё работало комфортно при тупом парсинге с начала при каждом вводе символа (но лимит тогда был 10000 байт кода).
Re[2]: Комментарии
От: Serge  
Дата: 26.08.20 08:57
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>Здравствуйте, Serge, Вы писали:


S>>Есть такая задача с одного из конкурсов.


VVV>Если нет ограничений по времени, то и задачи-то нет — парси каждый раз с начала и смотри коммент это или нет.


2 sec.
Re: Комментарии
От: Chorkov Россия  
Дата: 02.09.20 14:48
Оценка:
Здравствуйте, 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)) обращений к отрезкам.
Должны уложиться.
Re[2]: Комментарии
От: Serge  
Дата: 21.09.20 09:55
Оценка:
Здравствуйте, Chorkov, Вы писали:

 private class Solver {
        private int next[][] = {
            new int[] { 0, 1, 0 }, // I
            new int[] { 0, 1, 2 }, // /
            new int[] { 2, 2, 3 }, // /*
            new int[] { 2, 4, 3 }, // *
            new int[] { 0, 1, 0 }, // */
        };
        private int mark[][] = {
            new int[] { 0, 0, 0 }, // I
            new int[] { 0, 0, 1 }, // /
            new int[] { 1, 1, 1 }, // /*
            new int[] { 1, 1, 1 }, // *
            new int[] { 1, 1, 1 }, // */
        };
        private int state[][][];
        private int chars[];

        public Solver(String s) {
            chars = new int[s.length() + 2];
            for (int i = 0; i < s.length(); ++i) {
                chars[i + 1] = "./*".indexOf(s.charAt(i));
            }
            state = new int[4 * chars.length][][];
            for (int i = 0; i < state.length; ++i) {
                state[i] = new int[5][];
                for (int j = 0; j < 5; ++j) {
                    state[i][j] = new int[2];
                }
            }
            build(0, 0, chars.length - 1);
        }

        public void set(int pos, char c) {
            set(0, 0, chars.length - 1, pos, c);
        }

        private void set(int node, int lo, int hi, int pos, char c) {
            if (lo == hi) {
                chars[pos] = "./*".indexOf(c);
            } else {
                int xx = (lo + hi) / 2;
                if (pos <= xx) {
                    set(2 * node + 1, lo, xx, pos, c);
                } else {
                    set(2 * node + 2, xx + 1, hi, pos, c);
                }
                update(node, xx);
            }
        }

        public boolean get(int pos) {
            return mark[get(0, 0, 0, chars.length - 1, pos)][chars[pos + 1]] > 0;
        }

        private int get(int node, int init, int lo, int hi, int pos) {
            if (lo == pos) {
                return state[node][init][0];
            }
            if (hi == pos) {
                return state[node][init][1];
            } else {
                int xx = (lo + hi) / 2;
                if (pos <= xx) {
                    return get(2 * node + 1, init, lo, xx, pos);
                } else {
                    int l[] = state[2 * node + 1][init];
                    int t = next[l[1]][chars[xx + 1]];
                    int r[] = state[2 * node + 2][t];
                    return get(2 * node + 2, r[0], xx + 1, hi, pos);
                }
            }
        }

        private void build(int node, int lo, int hi) {
            if (lo == hi) {
                for (int s = 0; s < 5; ++s) {
                    state[node][s][0] = s;
                    state[node][s][1] = s;
                }
            } else {
                int xx = (lo + hi) / 2;
                build(2 * node + 1, lo, xx);
                build(2 * node + 2, xx + 1, hi);
                update(node, xx);
            }
        }

        private void update(int node, int xx) {
            for (int s = 0, t; s < 5; ++s) {
                int[] l = state[2 * node + 1][s];
                t = next[l[1]][chars[xx + 1]];
                int[] r = state[2 * node + 2][t];
                state[node][s][0] = s;
                state[node][s][1] = r[1];
            }
        }
    }
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.