Интересная задача

[makskovalko]

Помогите решить задачу!

Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1

[VIK_aka_TOR]

наверное сперва разбить строку на массив слов, затем уже прогонять проверки на повторение слов, считать индекс и т.д...
допустим разбили на массив слов используя функции pos, для искомой подстроки ставим пробел, и будет функция возвращать на каком месте он находится, а дальше копировать от начала строки до места на который указывает pos, удаляем то что скопировали, и вновь через pos ищем где след пробел и так до окончания строки.

а по словам уже обычным сравниваем элементов массива, проставлением индексов и т.д...

[BDA]

Не знаю, насколько получится затратно.

Я бы построил дерево:
52 указателя на поддеревья (по количеству букв)
каждый элемент дерева (кроме корня) хранит порядковый номер (если есть слово, заканчивающееся на этом элементе) и указатели на следующие 52 поддерева
Таким образом, при считывании очередного символа, мы идем по дереву, пока не дойдем до конца слова (при необходимости достраивая дерево). Если элемент дерева хранит нулевой номер, то назначаем последний незанятый, иначе выводим хранимый номер.

Такой вариант может не пройти по количеству памяти, но по времени, на мой взгляд, он более оптимален.