LUCKY STRING（微軟校招）

題目描述

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.

示例1

輸入

複制

aabcd

輸出

複制

a

aa

aab

aabc

ab

abc

b

bc

bcd

c

cd

d

題意：若一個串的某個子串中元素集合的個數是一個斐波那契數，則它就是幸運串，以字典序輸出一個串中的所有幸運串。

思路：資料溫暖，set + 暴力 + 預處理數值小于26的斐波那契表。

#include<bits/stdc++.h>
  using namespace std;
   set<int> jj;
    void init()
    {
         vector<int> a;
           a.push_back(1);
             a.push_back(1);
               jj.insert(1);
          int i = 2;
        while(a[i-1] + a[i-2] <= 26)
        {
              int doll = a[i-1] + a[i-2];
                 jj.insert(doll);
                   a.push_back(doll);
                     ++i;
        }
    }
  int main()
  {
       char s[110];
          set<string> v;
         gets(s);
       init();
      for(int i = 0 ; s[i] ; ++ i)
      {
          string ss = "";
           set<char> SET;
            ss += s[i];
              v.insert(ss);
               SET.insert(s[i]);
            for(int j = i + 1 ; s[j] ; ++ j)
            {
                  ss += s[j];
                    SET.insert(s[j]);
                   if(jj.count(SET.size()))v.insert(ss);
            }
      }
     set<string> :: iterator it = v.begin();
         while(it != v.end())
         {
              cout << *it << endl;
              it++;
         }
  }