#include<iostream>
#include<string>
#include <set>
using namespace std;
#define repeat(end) for(int _i=0;_i<end;_i++)
int fibo[]={1,1,2,3,5,8,13,21,34,55,89};
set<string> out;
int main()
{
	string str;
	cin>>str;
	repeat(str.size())
	{
		set<char> m;
		int f=1;
		for(int i=_i;i<str.size();i++)
		{
			m.insert(str[i]);
			if(m.size()==fibo[f])
			{
				out.insert(str.substr(_i,i-_i+1));
			}
			else if(m.size()==fibo[f+1]) 
				i--,f++;
		}
	}
	for(auto itor=out.begin();itor!=out.end();itor++)
	{
		cout<<*itor<<endl;
	}
	return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<Integer> fib = new HashSet<>();
        for (int i = 1, j = 0, t; i+j < 100;) {
            fib.add(i+j);
            t = i;
            i += j;
            j = t;
        }
        System.out.println(fib);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            TreeSet<String> treeSet = new TreeSet<>();
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j <= s.lengt敏感词reeSet.add(s.substring(i, j));
                }
            }

            for (String string : treeSet) {
                HashSet<Character> chs = new HashSet<>();
                for (int i = 0; i < string.length(); i++) {
                    chs.add(string.charAt(i));
                }
                if(fib.contains(chs.size()))
                    System.out.println(string);
            }
        }
    }
} 

	using System;



	using System.Linq;



	using System.Collections.Generic;



	 



	namespace LUCKYSTRING



	{



	    classMainClass



	    {



	        privatestaticList<int> dp = newList<int>();



	        publicstaticvoidMain(string[] args)



	        {



	            string line;



	 



	            dp.Add(0);



	            dp.Add(1);



	            dp.Add(1);



	            for(inti = 3; i <= 20; ++i)



	            {



	                dp.Add(dp[i - 1] + dp[i - 2]);



	            }



	            Dictionary < string, int> dic = newDictionary<string, int>();



	            while(!string.IsNullOrEmpty(line = Console.ReadLine()))



	            {



	                dic.Clear();



	                for(inti = 0; i < line.Length; ++i)



	                {



	                    for(intj = i; j < line.Length; ++j)



	                    {



	                        string temp = line.Substring(i, j - i + 1);



	                        if(isLuckString(temp))



	                        {



	                            if(!dic.ContainsKey(temp))



	                            {



	                                dic.Add(temp, 1);



	                            }



	                        }



	                    }



	                }



	                Dictionary<string, int> dicRet = dic.OrderBy(p => p.Key).ToDictionary(p => p.Key, p => p.Value);



	                foreach (KeyValuePair<string, int> item in dicRet)



	                {



	                    Console.WriteLine(item.Key);



	                }



	            }



	        }



	 



	        privatestaticbool isLuckString(string str)



	        {



	            List<char> list = newList<char>();



	            for(inti = 0; i < str.Length; ++i)



	            {



	                if(!list.Contains(str[i]))



	                {



	                    list.Add(str[i]);



	                }



	            }



	            if(dp.Contains(list.Count))



	            {



	                returntrue;



	            }



	            else



	            {



	                returnfalse;



	            }



	        }



	    }



	}



	

//利用set去重，全局变量Fib根据需要动态添加元素，判断是否为fibonacci数.
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> Fib;
bool isFib(int n){
	if(Fib.size()<2){
		Fib.push_back(1);
		Fib.push_back(2); 
	}
    while(n>Fib.back())
        Fib.push_back(Fib[Fib.size()-2]+Fib[Fib.size()-1]);
    if(find(Fib.begin(),Fib.end(),n)==Fib.end())
        return false;
    return true;
}
int count(string s){
    int p[26]={0},R=0;
    for(int i=0;i<s.length();i++)
        if(p[s[i]-'a']==0){
        	R++;
        	p[s[i]-'a']=1;
    	}
    return R;    
}
int main(){
    string str;
    set<string> s;
    cin>>str;
    int n=1;
    while(n<str.length()){
        for(int i=0;i<=str.length()-n;i++){
            string ss=str.substr(i,n);
            if(isFib(count(ss)))
                s.insert(ss);
        } 
		n++;     
    }
    set<string>::iterator it;
    for(it=s.begin();it!=s.end();it++)
        cout<<*it<<endl;
    return 0;
}

def islucky(ss):#判断是否是幸运数字
    if len(set(ss)) in Fibonacci:
        return True
    else:
        return False

def string(ss):#求所有子字符串
    results = []
    for x in range(len(s)):# x + 1 表示子字符串长度
        for i in range(len(s) - x):# i 表示偏移量
            results.append(s[i:i + x + 1])
    return results

s=input()
Fibonacci=[1,2,3,5,8,13,21]#26以内的feibonacci数（26个字母）
ans=list(set(string(s)))#set去重
ans.sort()#按字典序排序
for i in ans:
    if islucky(i):
        print(i)

https://fanxinglanyu.blog.csdn.net/article/details/104621310

2.1 题意

判断当前字符串的所有子串不同字母的个数是否是斐波那契数，如果是，则输出，否则，继续判断下一个子串。

2.2 思路

• 打表，打印100以内的斐波那契数
• 用set<char>实现去重统计字符串个数，
• 每次判断当前子串的不同字母的个数是否是斐波那契数，如果是，则存入set<string>（是想按字典序排序的要求）；如果是下一个斐波那契数，重新判断，存入set<string>（是想按字典序排序的要求）；如果不是，继续判断下一个子串。
• 最后输出结果。

  3 参考代码

#include <cstring>
(803)#include <iostream>
#include <set>

using std::cin; using std::cout;
using std::set; using std::string;
using  std::endl;

int fib[] = {1,1,2,3,5,8,13,21,34,55,89};//打表
set<string> result;

int main()
{
    string str;
    cin >> str;
    int n = str.length();
    for(int i = 0; i < n; i++) {//遍历每个字符，确定子串的首字母
        set<char> s;//统计子串中的每个不同字符的数目
        int k = 1;
        for (int j = i; j < n; j++) {//固定首字母，增加剩余的字母
            s.insert(str[j]);
            if (s.size() == fib[k]) {//如果是斐波那契数，继续递增字母数量
                result.insert(str.substr(i, j - i + 1));//当前字符拼接从i开始长度为j-i+1的字符
            } else if (s.size() == fib[k + 1]) {//如果是下一个斐波那契数
                j--;//回头重新判断这个字符串（防止漏判）
                k++;//斐波那契数更新为下一个斐波那契数
            }
        }
    }

    for (auto it = result.begin(); it != result.end(); it++) {
        cout << *it << endl;
    }

    return 0;
}

s = input()

def fib():
    a, b = 0, 1
    while b <= 100:
        a, b = b, a+b
        yield a

luckys = set()

for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        sub = s[i: j]
        if len(set(sub)) in fib():
            luckys.add(sub)

luckys = list(luckys)
luckys.sort()
for lucky in luckys:
    print(lucky)

#include <bits/stdc++.h>

using namespace std;

int fib[] = {1,1,2,3,5,8,13,21,34,55,89};
set<string> result;

int main()
{     string str;     cin>>str;     int n = str.length();     for(int i=0;i<n;i++)     {         set<char> s;         int k = 1;         for(int j=i;j<n;j++)         {             s.insert(str[j]);             if(s.size() == fib[k])                 result.insert(str.substr(i,j-i+1));             else if(s.size() == fib[k+1])                 j--,k++;         }     }     for(auto it=result.begin();it!=result.end();it++)         cout<<*it<<endl;     return 0;
}

	

//常见做法，先求子串，然后判断字串字符个数是否属于菲波那切数，然后再去重放入容器，最后排序按字典输出。
#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include <algorithm>
using namespace std;
vector<string> str;
int count1 ,a[10] = {1,2,3,5,8,13,21,34,55,89};
void CF(string str2,int q){

    int e,r,count=0;
    int str3[100];
    for(e=0;e<q;e++){
        for(r=0;r<count;r++){
            if(str3[r] == str2[e]){
                break;
            }
        }
        if(r == count){
            str3[count] = str2[e];
            count++;
        }
    }
    for(e=0;e<10;e++){
        if(count == a[e]){
            break;
        }
    }

    if(e != 10){
		int t;
		for(t=0;t<count1;t++)
		{
			if( strcmp(str2.c_str(),str[t].c_str() ) == 0)
			{
				break;
			}
		}	
		if(t == count1){

			str.push_back(str2);
			count1++;
		}
    }
}
int main(){
    string str1,str2;
    while( cin >> str1 ){
		count1 = 0;
        int i,j,l = str1.length();
        for(i=0;i<l;i++){
            for(j=i;j<l;j++){
				str2 = str1.substr(i,j-i+1);
				CF(str2,str2.length());
            }
        }
		sort(str.begin(), str.end());
		for (i=0; i<count1; i++)
			cout << str[i]<< endl;
    }
    return 0;
}
//算法更新，利用set性质，统计字符串不同字符个数简化。
#include<iostream>
#include<string>
#include<set>//特殊性质可以自动排序（对字符串排序默认是按其字典序，切不重复录入！
using namespace std;
set<string> str;
int a[10] = {1,2,3,5,8,13,21,34,55,89};
int main(){
    string str1,str2;
    while( cin >> str1 ){
        int i,j,l = str1.length();
        for(i=0;i<l;i++){
            for(j=i;j<l;j++){
                int e,count = 0;
                str2 = str1.substr(i,j-i+1);
                for(e=97;e<=122;e++){//统计字符串中不同小写字母的个数，由于本题限定了输入的为小写字母 97到122 之间，故可用这种特殊方法。
        			if(str2.find(e) != string::npos)
            				count++;
                }
    			for(e=0;e<10;e++){
        			if(count == a[e])
            			break;
                }
    			if(e != 10)
        			str.insert(str2);
            }
        }
        for(auto it = str.begin();it!=str.end();it++)//auto 型，可以在声明变量时根据变量的初始值，自动进行类型匹配。
            cout<<*it<<endl;   
    }
    return 0;
}

LUCKY STRING

思路

1. 构造100以内的fibonacci数。
2. 取substring,判断是否是fibonacci数，可以用set保存substring的不同字符。

代码

public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        String s = in.next();

        // 构造fibonacci数set
        // 输入字符串不多于100，所以只需要构造100以内
        Set<Integer> fib = new HashSet<>();
        int a = 1;
        int b = 1;
        for (int i = 1; i <= 20; i++) {
            if (b > 100) break;
            fib.add(b);
            int sum = a + b;
            a = b;
            b = sum;
        }

        // 用来保存子串中的字符，set的size代表不同字符的个数
        Set<Character> temp = new HashSet<>();
        // treeSet用来排序结果
        Set<String> res = new TreeSet<>();
        for (int i = 0; i < s.length(); i++) {
            temp.add(s.charAt(i));
            for (int j = i; j < s.length(); j++) {
                if (j > i) temp.add(s.charAt(j));
                // 检查该数子是否是fibonacci数
                if (fib.contains(temp.size())) res.add(s.substring(i, j + 1));
            }
            temp.clear();
        }

        // 输出
        for (String s1 : res) {
            System.out.println(s1);
        }
    }

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String s = new Scanner(System.in).next();
        int a = 1, b = 1;
        HashSet<Integer> set = new HashSet<>();
        HashSet<String> list = new HashSet<>();
        for (int i = 3; i <= 50; i++) {
            set.add(b);
            int c = a + b;
            a = b;
            b = c;
        }
        HashSet<Character> dup = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            dup.add(s.charAt(i));
            for (int j = i; j < s.length(); j++) {
                if (j > i)
                    dup.add(s.charAt(j));
                if (set.contains(dup.size()))
                    list.add(s.substring(i, j + 1));
            }
            dup.clear();
        }

        String[] ss = list.toArray(new String[]{});
        Arrays.sort(ss);
        for (String s1 : ss) {
            System.out.println(s1);
        }
    }
}

// 抓住几个要点即可：
// 1. 寻找子字符串； 2.子字符串的不同字符个数；3.判断是不是fibnacci数
#include<bits/stdc++.h>
using namespace std;
int countDif(string s) {
    unordered_map<char, int> umap;
    for (auto item : s) {
        umap[item]++;
    }
    return static_cast<int>(umap.size());
}

bool isFib(int num) {
    int pre = 0;
    int cur = 1;
    int next = 0;
    while (next < num) {
        next = pre + cur;
        pre = cur;
        cur = next;
    }
    return num == next;
}

int main() {
    string s;
    cin >> s;
    unordered_map<string, int> si;
    vector<string> res;
    for (size_t i = 0; i < s.size(); ++i) {
        for (size_t j = i; j < s.size(); ++j) {
            string subs = s.substr(i, j-i+1);
            if (isFib(countDif(subs))) {
                if (si[subs]++ == 0)
                    res.push_back(subs);
            }
        }
    }
    sort(res.begin(), res.end());
    for (auto item : res)
        cout << item << endl;
    return 0;
}

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        //得到一个26以内的fibonacci的数组
        int[] fib= getFib(26);
        ArrayList<String> luckys = new ArrayList<>();//保存lucky子串
        
        Scanner in = new Scanner(System.in);
        String str = in.next();
        
        //获取所有不重复的子串
        Set<String> allSubStr= new HashSet<>();
        for(int i=0;i<str.length();i++){
            for(int j= i;j<str.length();j++){
                allSubStr.add(str.substring(i,j+1));
            }
        }
        
        //字典排序所有子串
        ArrayList<String> subList=new ArrayList<>();
        subList.addAll(allSubStr);
        Collections.sort(subList);
        
        //统计每个子串的不同字符数
        for(String item:subList){
            int[] flag = new int[26];
            int characters=0;
            for(int i=0;i<item.length();i++){
                flag[item.charAt(i)-'a'] = 1;
            }
            //统计flag中1的个数
            for(int j=0;j<26;j++){
                if(flag[j]==1) characters++;
            }
            
            //如果characters在fib数组中，那么这个item是lucky子串 ，输出，同时保存
            if(contains(fib,characters)){
                luckys.add(item);
                System.out.println(item);
            }
        }
        
        
    }
    
    
    //返回一个fibonacci数组 n是数组大小
    public static int[] getFib(int n){
        int[] res= new int[n];
        res[0]=1;
        res[1]=1;
 
        if(n==1||n==2) return res;
        int i= 2;
        while(i++<n-1){
            res[i] = res[i-1]+res[i-2];
        }
        return res;
    }
    
    //检查数组是否包含目标值
    public static boolean contains(int[] src,int target){
        for(int i:src){
            if(i == target) return true;
        }
        return false;
    }
}

//毫无疑问，必须穷举！
//然后问题的关键就是求一个字符串中不同元素的个数：
//    1，利用unique算法，把重复元素分离，计算剩余元素个数
//    2，利用在较小字符串的基础上，分析新加入字符的重复性，加1或者加0，类似动态规划
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void fill_fib(vector<int> &fib){
	int f1=1,f2=1;
	fib[1]=fib[2]=1;
	int f=0;
	while(f<=26){
		f=f1+f2;
		fib[f]=1;//f is fibonacci number,then fib[f]=1;
		f1=f2;
		f2=f;
	}
}
void work_out(string str,int **c,vector<string> &cands,vector<int> &fib){
	int n=str.size();
	for(int i=0;i<n;++i){
		c[i][i]=1;
		cands.push_back(string(str,i,1));
	}
	for(int l=2;l<=n;++l){
		for(int i=0;i<n+1-l;++i){
			int j=i+l-1;
			string::iterator p=find(str.begin()+i,str.begin()+j,str[j]);
			if(p==str.begin()+j)
				c[i][j]=c[i][j-1]+1;
			else
				c[i][j]=c[i][j-1];
			if(fib[c[i][j]]==1)
				cands.push_back(string(str.begin()+i,str.begin()+j+1));
		}
	}
}	
int main(){
	string str;
	cin>>str;
	int n=str.size();
	vector<int> fib(26,0);
	fill_fib(fib);
	vector<string> cands;
	int **c=new int*[n];
	for(int i=0;i<n;++i)
		c[i]=new int[n];
	work_out(str,c,cands,fib);
	sort(cands.begin(),cands.end());
	vector<string>::iterator u=unique(cands.begin(),cands.end());
	for(vector<string>::iterator ite=cands.begin();ite!=u;++ite)
		cout<<*ite<<endl;
	return 0;
}

import java.util.*;

public class Test {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		sc.close();
		//首先计算斐波那契数字，不多于100位意味着100之内的斐波那契数就行
		Set<Integer> fib=new HashSet<Integer>();
		for (int i = 1; i < 20; i++) {
			fib.add(fibonacci(i));
		}
		//拆分字符串
		Set<String> subStr=new HashSet<String>();
		for (int i = 0; i < str.length(); i++) {
			for (int j = i; j < str.length(); j++) {
				subStr.add(str.substring(i, j+1));
			}
		}
		//对子字符串集合进行排序
		ArrayList<String> strList=new ArrayList<String>();
		strList.addAll(subStr);
		Collections.sort(strList);
		//比对并输出
		Set<Character> chs=new HashSet<Character>();
		for (String s : strList) {
			char[] ch=s.toCharArray();
			for (char c : ch) {
				chs.add(c);
			}
			if (fib.contains(chs.size())) {
				System.out.println(s);
			}
			chs.clear();
		}
	}
	public static int fibonacci(int n){
		if (n==1||n==2) {
			return 1;
		}
		else {
			return fibonacci(n-1)+fibonacci(n-2);
		}
	}
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

//26个字母，数列最大21
int f[] = {1,2,3,5,8,13,21};

//判断个数
bool islucky(char *buf){
    int hash[26] = {0};
    int n = 0;
    for(int i = 0; i < strlen(buf); i++){
        if(hash[buf[i]-'a'] == 0){
            n++;
            hash[buf[i]-'a']++;
        }
    }
    for(int i = 0; i < 7; i++){
        if(n == f[i]) return true;
    }
    return false;
}

//字典序排序
int cmp(const void *a,  const void *b){
    return strcmp(*(char**)a, *(char**)b);
}

int main()
{
    char s[10000];
    scanf("%s", s);
    int n = strlen(s);
    char **ans  = malloc(sizeof(char *) * 10001);
    for(int i = 0; i < 10001; i++){
        ans[i] = malloc(sizeof(char) * n + 1);
    }
    int index = 0;
    char buf[n+1];
        //列出所有子序列
    for(int i = 0; i < n; i++){
        int top = 0;
        for(int j = i; j < n; j++){
            buf[top++] = s[j];
            buf[top] = '\0';
            strcpy(ans[index++], buf);
        }
    }
    qsort(ans, index, sizeof(char*), cmp);

        //只输出符合条件的子序列
    printf("%s\n",ans[0]);
    for(int i = 1; i < index; i++){
        if(islucky(ans[i]) && strcmp(ans[i], ans[i-1]) != 0)
            printf("%s\n",ans[i]);
    }
}