hihocoder #1152 Lucky Substrings

hihocoder #1152 Lucky Substrings 【字符串处理问题】strsub()函数+set集合去重 - 我喜欢旅行 - 博客园
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://algorithm.yuanbin.me/zh-hans/microsoft/mstest2015april2/problem_a_lucky_substrings.html

简单实现题，即判断 substring 中不同字符串的个数是否为 fibonacci 数，最后以字典序方式输出，且输出的字符串中相同的只输出一次。分析下来需要做如下几件事：

1. 两重 for 循环取输入字符串的所有可能子串。
2. 判断子串中不同字符的数目，这里使用可以去重的数据结构Set比较合适，最后输出Set的大小即为不同字符的数目。
3. 判断不同字符数是否为 fibonacci 数，由于子串数目较多，故 fibonacci 应该首先生成，由于字符串输入最大长度为100，故使用哈希表这种查询时间复杂度为 $O(1)$ 的数据结构。
4. 将符合条件的子串加入到最终结果，由于结果需要去重，故选用Set数据结构。

fibonacci 数组的生成使用迭代的方式，由于保存的是Long类型，故在判断子串 size 时需要将 size 转换为long. Java 中常用的 Set 有两种，无序的HashSet和有序的TreeSet.

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        Set<String> result = solve(input);
        for (String s : result) {
            System.out.println(s);
        }
    }

    public static Set<String> solve(String input) {
        Set<Long> fibonacci = fibonacci_number(input.length());
        Set<String> res = new TreeSet<String>();
        for (int i = 0; i < input.length(); i++) {
            for (int j = i + 1; j <= input.length(); j++) {
                String substr = input.substring(i, j);
                if (isFibonacci(substr, fibonacci)) {
                    res.add(substr);
                }
            }
        }

        return res;
    }

    public static boolean isFibonacci(String s, Set<Long> fibo) {
        Set<Character> charSet = new HashSet<Character>();
        for (Character c : s.toCharArray()) {
            charSet.add(c);
        }
        // convert charSet.size() to long
        if (fibo.contains((long)charSet.size())) {
            return true;
        } else {
            return false;
        }
    }

    public static Set<Long> fibonacci_number(int n) {
        // generate fibonacci number till n
        Set<Long> fibonacci = new HashSet<Long>();
        long fn2 = 1, fn1 = 1, fn = 1;
        fibonacci.add(fn);
        for (int i = 3; i <= n; i++) {
            fn = fn1 + fn2;
            fibonacci.add(fn);
            fn2 = fn1;
            fn1 = fn;
        }
        return fibonacci;
    }

题目分析：给你一个字符串，找出这个串的连续子串，但是我们不全部输出，只输出那些子串中不同字母数刚好也是斐波那契数的
子串。举例：子串：a（斐波那契数=1）合法；  aabcd(有4个不同字母，4不是斐波那契数) 不合法，不输出。
算法实现：用c++的strsub()函数，一次划分出每次子串，判断每个子串是否合法。如果合法，将其插入到STL set集合里面，这
样做也省去了去除重复子串的麻烦，输出集合set里面的内容时，是按顺序已经排好的。
http://www.cnblogs.com/yspworld/p/4510086.html

int main()

{

    string s, cur;

    set<string>t;

    cin>>s;

    int len=s.size();

    int i, j, k;

    int a[26];

    for(i=0; i<len; i++)

    {

        for(j=1; i+j<=len; j++)

        {

            cur = s.substr(i, j);

            //cout<<cur<<endl;

            int length=cur.size();

            memset(a,0,sizeof(a));

            for(k=0; k<length; k++)

            {

                a[cur[k]-97]=1;

            }

            int cnt=0;

            for(k=0; k<26; k++){

                if(a[k]>0)

                    cnt++;

            }

            if(cnt==1||cnt==2||cnt==3||cnt==5||cnt==8||cnt==13||cnt==21

               ||cnt==34||cnt==55||cnt==89)

               t.insert(cur);

        }

    }

    set<string>::iterator it=t.begin();

    while(it!=t.end())

    {

        cout<<*it<<endl;

        it++;

    }

    return 0;

}

http://m.blog.csdn.net/blog/violet_echo_0908/47205465

void fib(){             //先标记好110以内的斐波那契数，后面用 
    memset(n, 0, sizeof(n));
    n[0] = n[1] = 1;
    int i = 2, a = 1, b = 2;
    while(b < 110){
        n[b] = 1;
        int t = a+b;
        a = b;
        b = t;
    }
}

int main() {
    fib();
    string str;
    int a[26];
    while(cin >> str){
        string c;
        int len = str.size();
        for(int i = 0; i < len; i++){
            for(int j = 1; i+j <= len; j++){
                c = str.substr(i, j);
                int leng = c.size();
                memset(a, 0, sizeof(a));

                for(int k = 0; k < leng; k++)        
                    a[c[k]-97] = 1;     //每找到一个子串，就用数组a标记哪些字母出现过

                int co = 0;
                for(int k = 0; k < 26; k++){   //用co记录字串中出现的字母数 
                    if(a[k])
                        co++;
                }
                if(n[co])   //判断出现的字母数是不是斐波那契数 
                    t.insert(c);
            }
        }
        set<string>::iterator i = t.begin();
        while(i!=t.end()){
            cout << *i << endl;
            i++;
        }
    }
    return 0;
}

Read full article from hihocoder #1152 Lucky Substrings 【字符串处理问题】strsub()函数+set集合去重 - 我喜欢旅行 - 博客园