# hihoCoder week 84-1-Lucky Substrings

hihoCoder week 84-1-Lucky Substrings

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

```#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
set<int> FIB_NUM = { 1,2,3,5,8,13,21 };
int main() {
string s;
cin >> s;
set<string> ans;
int n = s.size();
for (int i = 0; i < n; i++) {
vector<bool> alphabet(26, false);
int cnt = 0;
for (int j = i; j < n; j++) {
if (!alphabet[s[j] - 'a']) {
alphabet[s[j] - 'a'] = true;
cnt++;
}
if (FIB_NUM.find(cnt) != FIB_NUM.end()) {
ans.insert(s.substr(i, j - i + 1));
}
}
}
set<string>::iterator it = ans.begin();
while (it != ans.end()) {
cout << *it << endl;
it++;
}
return 0;
}
```