Язык пришельцев

"Язык пришельцев" (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.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *