Problem A. Lucky Substrings · Data Structure and Algorithm notes

Problem A. Lucky Substrings · Data Structure and Algorithm notes

A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters, output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once.

+

输入

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.

+

样例输入

aabcd 

样例输出

a aa aab aabc ab abc b bc bcd c cd d 

题解

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

+

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

Read full article from Problem A. Lucky Substrings · Data Structure and Algorithm notes