Недавно прошел первый квалификационный раунд конкурса Google Code Jam. Я в нем не участвовал, но, ради развлечения, решил одну из задач - alien language.
Суть задачи такова: у нас есть две последовательности строк. Первая, состоит из N разных строк одинаковой длины(abc, cda, ...). Вторая - из М строк вида: (abc)cd, где в скобках перечислены все возможные значения, которые являются шаблонами для поиска в первой последовательности. К примеру, шаблону (abc)cd, будут соответствовать три строки - acd, bcd и ccd. Цель - посчитать количество строк из первой последовательности, которые соответствуют каждому из шаблонов из второй последовательности.Решение в лоб - создать хэш таблицу из элементов первой последовательности. Затем для каждого из шаблонов, получить список всех возможных строк, которые соответствуют данному шаблону. После этого нужно выполнить поиск каждой из созданных строк в хэш таблице. Нам нужно определить количество удачных операций поиска для каждого из шаблонов.
Не трудно понять, что уже при достаточно небольшой длине строки, мы получим комбинаторный взрыв. Количество вариантов, которые нужно проверить будет огромным.
Самое простое решение задачи - преобразовать каждый из шаблонов в регулярное выражение, а затем посчитать количество совпадений. Но, это совсем не интересно :)
Вместо этого, я построил свой алгоритм, который не перебирает все возможные строки, подходящие к шаблону. Он ищет(и считает) совпадения в дереве, каждый узел которого может содержать до 26-ти потомков(на рисунке). Каждый из потомков соответствует одному из символов английского алфавита. Первому уровню дерева(узел показан зеленым цветом) соответствуют первые символы всех строк входной последовательности. Второму уровню(показан синим) - вторые символы, и так далее... Соответственно, что-бы проверить, есть-ли строка "abc" среди входных данных, нужно проверить, есть-ли в корневом узле дерева, поддерево, соответствующее символу 'a', затем, рекурсивно, найти в этом поддереве потомка, соответствующего символу 'b' и тд. Затем, если мы прошли ветвь дерева, соответствующую строке "abc", мы легко можем перейти к ветви, соответствующей подстроке "abd" либо "abb". В общем, алгоритм обхода дерева достаточно очевиден.
Работает это правильно и достаточно шустро. Я не измерял время работы, но по ощущениям, большой набор данных, был обработан не больше чем за две секунды :)
