← 返回题目列表

Codeforces · 928/D

D. 自动完成

中文机器翻译题面 查看原题

Arcady 是一名文案撰稿人。他今天的任务是使用他最喜欢的文本编辑器输入一个已经精心设计的故事。

Arcady 依次输入单词、标点符号和空格。每个字母和每个符号(包括换行)都需要单击一下键盘才能打印。此外,当 Arcady 在屏幕上具有某个单词的非空前缀时,编辑器会建议该单词的可能自动补全,更准确地说是已打印的单词之一,以便如果该单词是唯一的,则其前缀与当前打印的前缀相匹配。例如,如果Arcady已经再次打印了《codeforces》、《coding》和《codeforces》,那么将不会尝试自动完成《cod》,但如果他继续打印《code》,编辑器将建议《codeforces》。

只需单击一下,Arcady 就可以遵循编辑器的建议,即将当前前缀转换为它。请注意,自动完成后不会打印任何其他符号(无空格、换行符等)。如果不允许 Arcady 移动光标或删除已打印的符号,那么他最少需要按多少次键盘才能打印整个文本?

这里的单词是由空格、标点符号和行/文本开头/结尾组成的连续拉丁字母序列。 Arcady 仅使用小写字母。例如,“众所周知,井字游戏是两个玩家 x 和 o 的纸笔游戏”,其中有 20 个单词。

输入

唯一一行包含 Arcady 的文本,仅由小写拉丁字母、空格、换行符和以下标点符号组成:《.》、《,》、《?》、《!》、《'》和《-》。符号总数不超过3·105。保证所有行都非空。

输出

打印单个整数 — 最小点击次数。

示例

输入 #1

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

输出 #1

141

输入 #2

'co-co-co, codeforces?!'

输出 #2

25

输入 #3

thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

输出 #3

183

注意

在示例案例一中,最好在输入“sn”后对“snowboarding”的第一个实例使用自动完成功能,并在输入“snowb”后对“snowboarding”的第二个实例使用自动完成功能。这将节省 7 次点击。

在示例案例二中,是否使用自动完成并不重要。