题目描述
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.
程序代码
#include <iostream>
#include <vector>
#include <string> //#include <string.h>会报错
using namespace std;
int totalcharater(char *str){
int m[26];
for(int i=0;i<26;i++) //将m数组初始化为0
m[i]=0;
int count=0;
while(str[count]!='\0'){
int t=str[count]-97;
m[t]+=1;
count++;
}
int sum=0;
for(int i=0;i<26;i++){
if(m[i]>0)
sum++;
}
return sum;
}
bool iffibonacci(int n){
if(n==1||n==2||n==3||n==5||n==8||n==13||n==21)
return true;
else
return false;
}
bool ifrepeate(vector<string> &res,string str){
for(int i=0;i<res.size();i++){
if(res[i].compare(str)==0)
return true;
}
return false;
}
void strsort(vector<string> &res){
for(int i=0;i<res.size()-1;i++){
for(int j=0;j<res.size()-i-1;j++){
if(res[j].compare(res[j+1])>0){
string strtp;
strtp=res[j];
res[j]=res[j+1];
res[j+1]=strtp;
}
}
}
}
int main(){
char str[100];
scanf("%s",&str);
vector<string> res; //vector<char*> res; 字符串排序
int i=0;
while(str[i]!='\0'){
int j=i;
while(str[j]!='\0'){
char strtp[100];
int c=0;
for(int x=i;x<=j;x++){ //把子串赋值给strtp
strtp[c]=str[x];
c++;
}
strtp[c]='\0'; //字符串末尾以0结束
int difnum=totalcharater(strtp); //统计不同字符串个数
if(iffibonacci(difnum)){
string strin(strtp);
if(!ifrepeate(res,strin)) //判断是否重复
res.push_back(strin);
}
j++;
}
i++;
}
strsort(res);
for(int a=0;a<res.size();a++){
cout<<res[a]<<endl;
}
system("pause");
}