hihoCoder week 84-1-Lucky Substrings | bitJoy > code

hihoCoder week 84-1-Lucky Substrings | bitJoy > code

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

---

如果一个字符串中不同字母的个数是斐波那契数，则称这个字符串是Lucky的，问字符串S中哪些子串是Lucky子串。

要正确理解Lucky的定义，是不同字母的个数，而不是不同字母的个数序列。比如aabc是Lucky的，因为其有a,b,c共3种字母，而3在斐波那契数列中，所以aabc是Lucky的。不能理解为aabc中a出现2次，b,c分别出现1次，构成1,1,3是斐波那契数列，所以aabc是Lucky的。

所以只能枚举所有子串，判断每个子串是否为Lucky的。如果知道了S[i,...,j]中不同字母的个数，判断S[i,...,j+1]时，只要判断S[j+1]这个字母是否在之前出现过。所以通过保存之前不同字母的个数，可以快速判断S[i,...,j+1]的情况。

Read full article from hihoCoder week 84-1-Lucky Substrings | bitJoy > code