Цитата(ksili @ 15.2.2011, 05:46  ) |
| А нельзя в map слова сразу загнать так, чтобы они были отсортированы по-убыванию? В смысле, чтобы самое длинное слово находилось гарантировано первым, и не нужно было бы гонять цикл. |
Мне это первое что захотелось сделать, но отсортировать так нельзя.
map должен быть отсортирован по алфавиту, иначе бинарный поиск в нем не будет работать.
| Цитата(maxim1000 @ 15.2.2011, 09:43 ) |
| есть такая штука std::lower_bound |
lower_bound это нижняя граница. map отсортирован по алфавиту. Я специально привел пример, где 2 подходящих слова, а между ними может быть очень много не подходящих. Так что lower_bound здесь просто не имеет смысла.
| Цитата(1000000dollars @ 15.2.2011, 08:45 ) |
| Можно. Словарь делаешь деревом: в вершинах маркеры концов строк, рёбра - буквы. Слово начинается с корня и при добавлении проходится уже существующий путь и достраиваются ветки, а при поиске идём по дереву, пока есть соответствие потоку. Если остановились в вершине с маркером - значит искомое слово - путь от корня до текущей вершины, если по дереву путь прервался - поднимаемся по дереву до маркера конца слова. |
Вот здесь я честно говоря не понял. Не могли бы вы нарисовать это дерево на моем примере.
| Цитата(Pavia @ 15.2.2011, 13:45 ) |
| Можно детерминированный автомат построить. Будет O(n) вопрос только в том хватит ли вам памяти? Словарь большой? |
Да словарь вообще-то большой. Но, допустим, вот мой пример это все что есть. как это будет выглядеть примерно?
Добавлено через 6 минут и 51 секунду
to
ksili,
maxim1000,
еще раз хочу сказать, что ваши идеи мне понятны, но я не знаю способа отсортировать словарь, таки образом, чтобы подходящие слова были рядом. Если можете приведите способ такой сортировки.
)