首页 > 试题广场 >

LUCKY STRING

[编程题]LUCKY STRING

热度指数：12040 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

算法知识视频讲解

牛客34984249号

#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]);
    }
}

发表于 2021-07-15 11:17:57 回复(0)