Все же любят на досуге порешать задачки? Математические, логические, алгоритмические... нет? Ну ладно ;)

Недавно попалась интересная задача по программированию: реализовать функцию, проверяющую совпадение строки с шаблоном с поддержкой мета-символов * и . Короче, сильно упрощенные регулярные выражения. Дополнительным условием являлось то, что строка должна совпадать целиком.

С мета-символом . в таких условиях проблем не возникает, а вот * доставляет массу проблем. Комбинация из опциональных и обязательных символов заставляет "помнить историю" при разборе строки. С учётом этого обстоятельства, в одном из тестов проверка совпадения строки aaaaaaaaaaaaaaaaaaab с шаблоном a*a*a*a*a*a*a*a*a*a* занимала неприлично много времени.

Я пробовал разные подходы и в конце концов пришёл к тому, что шаблон можно упростить.

Правил упрощения сразу родилось два:

1. Если комбинация "символ со звёздочкой" повторяется несколько раз подряд, комбинацию можно оставить в единственном экземпляре. Таким образом, шаблон a*a*a*a*a*a*a*a*a*a* сокращается до a*. Естественно, символ перед звёздочкой должен быть один и тот же.
2. Комбинация .* включает в себя все остальные комбинации со звёздочкой. Поэтому подряд стоящие a*.*b* могут быть сокращены до .*. Обратите внимание, порядок не играет тут никакой роли, потому что * означает любое количество повторений предстоящего символа, включая его отсутствие. Поэтому и строка aaabbb и строка bca подходят под оба шаблона.

Первое правило универсально и его вполне можно распространить на все варианты применения регулярных выражений. Второе правило справедливо лишь в контексте решаемой задачи - проверить строку на совпадение.