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
微软的题目。
字符串处理，主要是找到子串，然后判断子串里不同的字符数。主要由三个难点： 1、判断子串里不同字符个数，可以用一个大小为26char数组来解决：如果出现过就置1，如果没有出现过就是默认的0.（用count函数解决） 2、主要就是要生成全部的substring，以及26以内的fibonacci数列。
26以内的fibonacci数列只有 1 2 3 5 8 13 21 34 55 89,用一个const int数组可以表示。然后用STL里的find函数来判断是否为fibonacci数列。 3、构建子串，用STL里的string的substr(int i,size_t size)可以解决。
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std; int count(string s) {
int p[] = { }, R = ;
for (int i = ; i<s.length(); i++)
if (p[s[i] - 'a'] == ) {
R++;
p[s[i] - 'a'] = ;
}
return R;
}
int main() {
string str;
set<string> s;
cin >> str;
const int fibonacci[] = { ,,,,,,};
vector<int> vec1(fibonacci, fibonacci + ); int n = ;
while (n<str.length()) {
for (int i = ; i <= str.length() - n; i++) {
string ss = str.substr(i, n);
if (find(vec1.begin(), vec1.end(), count(ss)) != vec1.end())
s.insert(ss);
}
n++;
}
set<string>::iterator it;
for (it = s.begin(); it != s.end(); it++)
cout << *it << endl;
return ;
}