hihocoder Lucky Substrings

淩亂°似流年 2022-08-02 01:53 138阅读 0赞

# 题目 #

时间限制:10000ms  
单点时限:1000ms  
内存限制:256MB  
描述  
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  
题目来源：[http://hihocoder.com/problemset/problem/1152?sid=443673][http_hihocoder.com_problemset_problem_1152_sid_443673]

# 分析 #

包含的知识点：  
1. 求字符串中出现的不同的字母个数。用hash表解决。  
2. 字典序输出。可以试试trie树，但是set内部是用红黑树实现的，无论插入的顺序如何，输出总是有序的，这就方便了好多。  
3. 判断一个数是否是fibonacci 数。也用hash表解决吧，数组下标如果是fibonacci 数，则把此下标对应的数组值置1.  
分析了知识点以后，基本上代码也就出来了，一点一点实现吧。

# 代码 #

#include <iostream>
    #include <string>
    #include <vector>
    #include <set>
    using namespace std;
    int diffChar(string str){
       //查找字符串中包含的不同字符的个数
        vector<int> help(26, 0);
        for(char c : str){
            help[c - 'a'] = 1;
        }
        int ans = 0;
        for(int n : help)
            ans += n;
        return ans;
    }
    void findLuckySubstr(string str, set<string> &ans){
        vector<int> help(101, 0);
        help[0] = 1;
        help[1] = 1;
        int fn_1 = 1, fn_2 = 0, fn = 0;
        while(fn < 101){
       //fibonacci 数组，100以内，如果下标是fibonacci 数，则数组值为1.
            fn = fn_1 + fn_2;
            if(fn < 101){
                help[fn] = 1;
                fn_2 = fn_1;
                fn_1 = fn;
            }
        }
        int len = str.length();
        for(int i = 0; i < len; i++)//所有的子字符串
            for(int j = 1; j <= len - i; j++){
                string tmp = str.substr(i, j);
                int num = diffChar(tmp);
                if(help[num] == 1)
                    ans.insert(tmp);
            }
    }
    int main(){
        string str;
        cin >> str;
        set<string> ans;//用个set可以实现lexicographical order
        findLuckySubstr(str, ans);
        set<string>::iterator it = ans.begin();
        for( ;it != ans.end(); it++)
            cout << *it << endl;
        return 0;
    }

[http_hihocoder.com_problemset_problem_1152_sid_443673]: http://hihocoder.com/problemset/problem/1152?sid=443673