Autocompletion
Contest: VK Cup 2018 - Квалификация 1
Difficulty rating: 1900
Tags: *special, strings, trees

Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.

Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «codeforces», «coding» and «codeforces» once again, then there will be no autocompletion attempt for «cod», but if he proceeds with «code», the editor will propose «codeforces».

With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols?

A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.».

Input format:
The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «.», «,», «?», «!», «'» and «-». The total amount of symbols doesn't exceed 3·105. It's guaranteed that all lines are non-empty.

Output format:
Print a single integer — the minimum number of clicks.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In sample case one it's optimal to use autocompletion for the first instance of «snowboarding» after typing up «sn» and for the second instance of «snowboarding» after typing up «snowb». This will save 7 clicks.

In sample case two it doesn't matter whether to use autocompletion or not.

Example input:
snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.

Example output:
141

Example input:
'co-co-co, codeforces?!'

Example output:
25

Editorial:
Изначально выделим все слова, которые есть в тексте. Количество остальных символов прибавим к ответу. Также нужно не забыть добавить к ответу количество строк во входных данных, так как каждая строка завершается переводом строки (это ещё одно нажатие на клавишу).
После этого будем решать задачу для набора слов с помощью бора. В вершине бора будем хранить массив номеров вершин — в какую вершину есть переход из текущей вершины по каждой букве латинского алфавита. Также будем хранить количество слов, которые имеют префикс, заканчивающийся в текущей вершине, и будем хранить информацию о том, оканчивалось ли хоть одно слово в текущей вершине.
Теперь будем обрабатывать все слова по порядку. Пойдем по текущему слову и найдем первую вершину в боре, которая соответствует переходу по текущей букве строки, и существует ровно один префикс из ранее рассмотренных слов, оканчивающийся в этой вершине. Если такого нет, то прибавим к ответу длину рассматриваемой строки (так как придётся все слово набирать целиком).
Если же такая вершина есть, то будем действовать следующим образом. Пусть мы посмотрели первые pos букв строки (то есть стоим сейчас в позиции pos, так как работаем в 0-индексации). Пойдем дальше по строке с позиции pos (сохраним значение pos в startPos). Будем увеличивать pos до тех пор, пока количество префиксов, оканчивающихся в соответствующей вершине бора, равно одному.
Пусть endPos — это первая буква в строке, для которой предыдущее условие нарушилось. Тогда, если вершина бора, в которой мы остановились, не является листом, нужно прибавить к ответу длину текущей строки.
В противном случае, буквы с startPos до endPos - 1 (включительно), мы можем набрать с помощью одного нажатия на клавишу автодополнения, и нужно прибавить к ответу startPos (так как эти буквы мы введём без автодополнения), прибавить один (это нажатие на кнопку автодополнения) и прибавить разность между длиной строки и endPos (так как иногда останется ненабранный суффикс, который нужно набрать руками после использования автодополнения).
После получения ответа для каждой строки si, нужно добавлять её в бор обычным образом. Если после добавления всего слова, вершина бора, соответствующая переходу по последней букве текущей строки, не является листом, то мы впервые встретили слово si и нужно вновь пройти по строке и увеличить на один количество префиксов, оканчивающихся в вершинах бора, соответствующих переходу по каждой из букв строки si.