"Язык пришельцев" (Alien Language) - Задача А предварительного раунда Google Code Jam 2009.
Задача
После многих лет исследований, ученые в Google Labs обнаружили передачу на языке пришельцев, идущую с далекой планеты. Язык пришельцев уникален в том, что каждое слово состоит ровно L строчных букв. Также в этом языке ровно D слов.
После составления словаря всех слов языка пришельцев, следующим откытием было обнаружение того, что пришельцы передавали сообщения на Землю в течении последнего десятилетия. К сожалению, их сигналы были ослаблены расстоянием между нашими планетами и некоторые слова могут быть неправильно синтерпретированными. В качестве помощи в раскодировании этих сообщений, ученые просят вас разработать алгоритм, определяющий число возможных интерпретаций для заданного шаблона.
Шаблон состоит ровно из L токенов. Каждый токен является либо одной строчной буквой (и ученые уверены, что это именно та буква), либо группой различных строчных букв, заключенной в скобки ( и ). Например: (ab)d(dc) означает, что первая буква или a, или b, вторая буква точно d, а последняя буква либо d, либо c. Таким образом шаблон (ab)d(dc) соответствует одному из этих четырех возможных: add, adc, bdd, bdc.
Вход
Первая строка входных данных содержит 3 целых числа, L, D и N, разделенных пробелом. Затем следует D строк, каждая из которых содержит одно слово длины L. Это известные слова из языка пришельцев. Затем следует N тестов, каждый на одной строке и содержащие по одному шаблону, описанному выше. Вы можете считать, что все приведенные известные слова уникальны.
Вывод
Для каждого теста выведите
Case #X: K
где X - номер теста, начиная с 1, и K обозначает, сколько слов языка пришельцев соответствуют заданному шаблону.
Ограничения
Малый набор данных
1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10
Большой набор данных
1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500
Пример
| Вход | Вывод |
3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc |
Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0 |
Сначала сохраним все заданные слова в двумерном массиве. После этого, читаем каждый шаблон, парсим его, и считаем, сколько слов ему соответствуют.
Одним из возможных способов хранения шаблона является двумерный < булев> массив P[15][26]. P[i][j] содержит значение True если i-й токен содержит j-ю букву алфавита и содержит значение False в противном случае. Другими словами, P[i] - битовая карта букв, содержащихся в i-м токене.
Парсинг можно делать так:
- читаем один символ c
- если c равен '(', читаем символы, пока не встретим ')'. Прочитанные символы являются токеном.
иначе токен состоит из символа c
- заполнить P[i] для символов в токене
Чтобы подсчитать, сколько слов подходит, мы для каждого слова проверяем чтобы каждая i-я буква содержалась в битовой карте P[i].
Сумарная сложность равна O(N * L * D).
На некоторые языках программирования эта задача может быть решена преобразованием шаблона в регулярное выражение. Например, в Питоне заменяем '(' и ')' на '[' и ']'.
Решение задачи на языке Си: blog.dataparksearch.org/174, использующее трюк перевода шаблонов в стандартные регулярные выражения и библиотечные функции regcomp и regexec.