Problem A. Lucky Substrings

单点时限:1000ms

内存限制:256MB

描述

A string consisting no more than 100 lower case letters.

输出

Output the lucky substrings in lexicographical order, one per line. Same
substrings should be printed once.

样例输出

题解

简单实现题，即判断 substring 中不同字符串的个数是否为 fibonacci 数，最后以字典序方式输出，且输出的字符串中相同的只输出一次。分析下来需要做如下几件事：

1. 两重 for 循环取输入字符串的所有可能子串。
2. 判断子串中不同字符的数目，这里使用可以去重的数据结构比较合适，最后输出Set的大小即为不同字符的数目。
3. 判断不同字符数是否为 fibonacci 数，由于子串数目较多，故 fibonacci 应该首先生成，由于字符串输入最大长度为100，故使用哈希表这种查询时间复杂度为 $$O(1)$$ 的数据结构。
4. 将符合条件的子串加入到最终结果，由于结果需要去重，故选用数据结构。

源码分析

遍历所有可能子串，时间复杂度 O(n^2), fibonacci 数组和临时子串，空间复杂度 O(n).