Lucky Substrings

描述

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

思路：暴力枚举。26以内斐波那契数打下表就可以了。用set去重排序。复杂度O(n*n*n);

我用前缀和，感觉并没有优化。

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<stdlib.h>
  6 #include<math.h>
  7 #include<cstdio>
  8 #include<queue>
  9 #include<stack>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 char cou[200];
 14 int fei[30];
 15 int flag[30];
 16 char dd[200];
 17 set<string>my;
 18 set<string>::const_iterator it;
 19 typedef struct pp
 20 {
 21     int al[26];
 22     pp()
 23     {
 24         memset(al,0,sizeof(al));
 25     }
 26 } ss;
 27 
 28 int main(void)
 29 {
 30     int n,i,j,k,p,q;
 31     fei[1]=1;
 32     fei[2]=1;
 33     for(i=3; i<30; i++)
 34     {
 35         fei[i]=fei[i-1]+fei[i-2];
 36         if(fei[i]>=26)
 37         {
 38             break;
 39         }
 40     }
 41     int zz=i;
 42     for(i=1; i<zz; i++)
 43         flag[fei[i]]=1;
 44     while(scanf("%s",cou)!=EOF)
 45     {
 46         my.clear();
 47         ss ak[200];
 48         int l=strlen(cou);
 49         int cnt=0;
 50         ak[cnt].al[cou[0]-‘a‘]++;
 51         for(i=1; i<l; i++)
 52         {
 53             ak[i].al[cou[i]-‘a‘]++;
 54             for(j=0; j<26; j++)
 55             {
 56                 ak[i].al[j]+=ak[i-1].al[j];
 57             }
 58         }
 59         int yy[26];
 60         for(i=0; i<l; i++)
 61         {
 62             for(int s=0; s<26; s++)
 63             {
 64                 yy[s]=ak[i].al[s];
 65             }
 66             int ans=0;
 67             for(int s=0; s<26; s++)
 68             {
 69                 if(yy[s])
 70                 {
 71                     ans++;
 72                 }
 73 
 74             }
 75             if(flag[ans])
 76             {
 77                 memset(dd,0,sizeof(dd));
 78                 int z=0;
 79                 int s;
 80                 for( s=0; s<=i; s++)
 81                 {
 82                     dd[z++]=cou[s];
 83                 }
 84                 my.insert(dd);
 85 
 86             }
 87         }
 88         for(i=0; i<l; i++)
 89         {
 90             for(j=i+1; j<l; j++)
 91             {
 92                 for(int s=0; s<26; s++)
 93                 {
 94                     yy[s]=ak[j].al[s]-ak[i].al[s];
 95                 }
 96                 int ans=0;
 97                 for(int s=0; s<26; s++)
 98                 {
 99                     if(yy[s])
100                     {
101                         ans++;
102                     }
103 
104                 }
105                 if(flag[ans])
106                 {
107                     memset(dd,0,sizeof(dd));
108                     int z=0;
109                     int s;
110                     for( s=i+1; s<=j; s++)
111                     {
112                         dd[z++]=cou[s];
113                     }
114                     my.insert(dd);
115                 }
116             }
117         }
118         for(it=my.begin(); it!=my.end(); it++)
119         {
120             cout<<*it<<endl;
121         }
122     }
123     return 0;
124 }

Lucky Substrings

原文：http://www.cnblogs.com/zzuli2sjy/p/5186440.html