Все же любят на досуге порешать задачки? Математические, логические, алгоритмические... нет? Ну ладно ;)
Недавно попалась интересная задача по программированию: реализовать функцию, проверяющую совпадение строки с шаблоном с поддержкой мета-символов *
и .
Короче, сильно упрощенные регулярные выражения. Дополнительным условием являлось то, что строка должна совпадать целиком.
С мета-символом .
в таких условиях проблем не возникает, а вот *
доставляет массу проблем. Комбинация из опциональных и обязательных символов заставляет "помнить историю" при разборе строки. С учётом этого обстоятельства, в одном из тестов проверка совпадения строки aaaaaaaaaaaaaaaaaaab
с шаблоном a*a*a*a*a*a*a*a*a*a*
занимала неприлично много времени.
Я пробовал разные подходы и в конце концов пришёл к тому, что шаблон можно упростить.
Правил упрощения сразу родилось два:
- Если комбинация "символ со звёздочкой" повторяется несколько раз подряд, комбинацию можно оставить в единственном экземпляре. Таким образом, шаблон
a*a*a*a*a*a*a*a*a*a*
сокращается до a*
. Естественно, символ перед звёздочкой должен быть один и тот же.
- Комбинация
.*
включает в себя все остальные комбинации со звёздочкой. Поэтому подряд стоящие a*.*b*
могут быть сокращены до .*
. Обратите внимание, порядок не играет тут никакой роли, потому что *
означает любое количество повторений предстоящего символа, включая его отсутствие. Поэтому и строка aaabbb
и строка bca
подходят под оба шаблона.
Первое правило универсально и его вполне можно распространить на все варианты применения регулярных выражений. Второе правило справедливо лишь в контексте решаемой задачи - проверить строку на совпадение.