| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Поиск строки в наборе шаблонов |
| Автор: ivans 10.12.2009, 13:20 |
| Приветствую, Мне нужно реализовать следующую задачу: имеется множество пар "шаблон - значение". Когда я получаю на вход некоторую строку, необходимо быстро найти значение, шаблон которого наиболее точно соответствует введённой строке. Допустим у меня есть следующие пары: "deck*" => 1 "de*" => 2 "*" => 3 Если я получаю на вход строку "deck123", должно быть выбрано значение 1. Если входная строка - "dekxxx", выбирается значение 2. Входная строка "pos123" выбирает значение 3. Сейчас я делаю это с помощью двух списков: первый содержит все шаблоны, начинающиеся не с метасимвола, второй - все шаблоны, первый символ которых - метасимвол (*, ? , [ и т.д.). Первый список отсортирован по первой букве шаблона а в пределах буквы - по убыванию длины префикса шаблона, не включаещего метасимволы. Второй список отсортирован по убыванию длины шаблона. Вначале я ищу первый элемент в списке 1, который начинается на ту же букву, что и введённая строка. Затем я просматриваю список последовательно до тех пор, пока первая буква остаётся неизменной и вызываю функцию сопоставления строки с шаблоном. Если сопоставление выполнено успешно, значение найдено. Если для выбранного отрезка из первого списка ни один шаблон не был успешно сопоставлен со входным значением, я последовательно просматриваю второй список от начала до конца, пока не будет найден совпадающий шаблон. Существуют ли готовые контейнеры (аналогичные STL map), которые позволяют выполнять подобного рода поиск? |
| Автор: xvr 10.12.2009, 13:37 |
| Смотрите в сторону 'Регулярных Выражений' (и 'Конечных Автоматов', конкретно NFA & DFA). DFA позволяет выяснить принадлежность строки к конкретному шаблону за 1 посимвольный просмотр этой строки |
| Автор: ivans 10.12.2009, 13:51 | ||
Как раз способ сопоставления строки с отдельным шаблоном меня не сильно волнует. Я скорее всего буду использовать обычный glob из libc, даже не regexp. Вопрос именно в наличии ассоциативного контейнера, который бы позволял находить элемент по наиболее точному соответствию ключа (который представляет собой шаблон) со входной строкой. |
| Автор: xvr 10.12.2009, 14:21 | ||
КА - это способ произвести сопоставление со ВСЕМИ шаблонами за 1 проход по исходной строке. Вот где такое взять готовое - не знаю (в свое время делал сам) |
| Автор: ivans 10.12.2009, 21:22 | ||||
Спасибо за пример! Попробую теперь понять, что там к чему... |