Недавно прошел первый квалификационный раунд конкурса Google Code Jam. Я в нем не участвовал, но, ради развлечения, решил одну из задач - alien language.
Суть задачи такова: у нас есть две последовательности строк. Первая, состоит из N разных строк одинаковой длины(abc, cda, ...). Вторая - из М строк вида: (abc)cd, где в скобках перечислены все возможные значения, которые являются шаблонами для поиска в первой последовательности. К примеру, шаблону (abc)cd, будут соответствовать три строки - acd, bcd и ccd. Цель - посчитать количество строк из первой последовательности, которые соответствуют каждому из шаблонов из второй последовательности.Решение в лоб - создать хэш таблицу из элементов первой последовательности. Затем для каждого из шаблонов, получить список всех возможных строк, которые соответствуют данному шаблону. После этого нужно выполнить поиск каждой из созданных строк в хэш таблице. Нам нужно определить количество удачных операций поиска для каждого из шаблонов.
Не трудно понять, что уже при достаточно небольшой длине строки, мы получим комбинаторный взрыв. Количество вариантов, которые нужно проверить будет огромным.
Самое простое решение задачи - преобразовать каждый из шаблонов в регулярное выражение, а затем посчитать количество совпадений. Но, это совсем не интересно :)
Вместо этого, я построил свой алгоритм, который не перебирает все возможные строки, подходящие к шаблону. Он ищет(и считает) совпадения в дереве, каждый узел которого может содержать до 26-ти потомков(на рисунке). Каждый из потомков соответствует одному из символов английского алфавита. Первому уровню дерева(узел показан зеленым цветом) соответствуют первые символы всех строк входной последовательности. Второму уровню(показан синим) - вторые символы, и так далее... Соответственно, что-бы проверить, есть-ли строка "abc" среди входных данных, нужно проверить, есть-ли в корневом узле дерева, поддерево, соответствующее символу 'a', затем, рекурсивно, найти в этом поддереве потомка, соответствующего символу 'b' и тд. Затем, если мы прошли ветвь дерева, соответствующую строке "abc", мы легко можем перейти к ветви, соответствующей подстроке "abd" либо "abb". В общем, алгоритм обхода дерева достаточно очевиден.
Работает это правильно и достаточно шустро. Я не измерял время работы, но по ощущениям, большой набор данных, был обработан не больше чем за две секунды :)
11 комментариев:
Как то уж очень сложно. Решение в лоб - просто сравнить каждое слово с шаблоном, а уж точно не генерировать все возможные слова. Решение поумнее - превратить шаблон во что-то более удобное (ака прекомпиляция шаблона).
Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db
Поздравляю! Вы изобрели бор :)
Да, я тоже простецки все сделал. Разобрал шаблоны просто в представление в памяти (map'ы) чтобы линейно не искать каждый раз. И потом просто для каждого слова проверял по map'у есть какая-то буква или нет.
Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db
Да, ваш вариант более правильный. Зато мой вариант позволяет не только считать совпадения, но и искать их. Хотя в данной задаче это совершенно не нужно :)
Поздравляю! Вы изобрели бор :)
Спасибо, буду знать как это называется xD
Дык и мой позволяет искать совпадения - я для каждой строчки проверяю, совпадает она или нет. Или я что-то неправильно понял?
> Или я что-то неправильно понял?
это я неправильно понял алгоритм, пардон ))
2Lazin: уточните свой алгоритм - вы строите дерево по множеству слов или по множеству шаблонов? Если первый вариант, то каким образом обрабатывается каждый шаблон?
2Lazin: уточните свой алгоритм - вы строите дерево по множеству слов или по множеству шаблонов? Если первый вариант, то каким образом обрабатывается каждый шаблон?
Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db
Да, ваш вариант более правильный. Зато мой вариант позволяет не только считать совпадения, но и искать их. Хотя в данной задаче это совершенно не нужно :)
Поздравляю! Вы изобрели бор :)
Спасибо, буду знать как это называется xD
Как то уж очень сложно. Решение в лоб - просто сравнить каждое слово с шаблоном, а уж точно не генерировать все возможные слова. Решение поумнее - превратить шаблон во что-то более удобное (ака прекомпиляция шаблона).
Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db
Отправить комментарий