#P2550. Zipf's Law

    ID: 1551 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>字符串哈希表排序Waterloo local 2001.06.02

Zipf's Law

题目描述

哈佛大学语言学教授 George Kingsley Zipf (190219501902-1950) 观察到,文本中第 kk 个最常见单词的频率大致与 1/k1/k 成正比。他在 19491949 年出版的《人类行为与最小努力原则》一书中解释了他的观察。尽管 Zipf 的理论基础已被广泛质疑,但这一规律仍然成立,并且其他人已经为其提供了更坚实的数学基础。

你的任务是找出在英文文本中恰好出现 nn 次的所有单词。单词是由字母组成的序列,单词之间由非字母字符分隔。大小写应忽略。单词可以是任意长度的英文单词。

输入格式

输入包含多个测试用例。每个测试用例的第一行是一个正整数 nn。随后是若干行文本,这些文本包含不超过 1000010000 个单词。每个测试用例的文本以一行 EndOfText 结束。EndOfText 不会出现在输入的其他地方,并且不被视为单词。

输出格式

对于每个测试用例,输出所有恰好出现 nn 次的单词,每个单词占一行,小写,按字母顺序排列。如果没有这样的单词,输出以下内容:

There is no such word.

测试用例之间用空行分隔。

输入样例 1

2

In practice, the difference between theory and practice is always
greater than the difference between theory and practice in theory.
	- Anonymous

Man will occasionally stumble over the truth, but most of the
time he will pick himself up and continue on.
        - W. S. L. Churchill
EndOfText

输出样例 1

between
difference
in
will

来源

200120016622 日滑铁卢地区赛(试题来源)