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
No comments:
Post a Comment