OR1. 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
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2022-01-20
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
//26个字母，数列最大21
int f[] = {1,2,3,5,8,13,21};
int l[26] = {0};
int h[27011] = {0};
int idx = 0;
struct data{
char a[100];
};
//struct data res[10000];
//判断个数
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){
char * a1 = (struct data *)a;
char * b1 = (struct data *)b;
return strcmp(a1,b1);
}
int find_lucky(int count) {
for(int i = 0; i < 7; i++){
if (f[i] == count) {
return i;
}
}
return -1;
}
int find_next_c(char * buf, char c, int s, int n) {
for(int i = s; i < n; i++) {
if (buf[i] == c) {
return i;
}
}
return -1;
}
int sum_s(char * buf, int n) {//no order
int sum = 0;
for(int i = 0; i < n; i++) {
sum += buf[i] - 'a' + 1 + i;
}
return sum;
}
void copy_s(char * s, char * d, int n) {
for(int i = 0; i < n; i++) {
d[i] = s[i];
}
}
void print_buf(char * buf, int s, int e, struct data res[]) {
struct data a;
char tmp[e-s+2];
for(int i = s; i <= e; i++) {
tmp[i-s] = buf[i];
//res[0].a[i-s] = buf[i];
}
tmp[e-s+1] = '\0';
//res[0].a[e-s+1] = '\0';
int sum_tmp = sum_s(tmp, e-s+1);
if (h[sum_tmp] == 0) {
h[sum_tmp] = 1;
copy_s(tmp, res[idx++].a, e-s+2);
//printf("%s\n",tmp);
} else {
bool flag = true;
for(int i = 0; i < idx; i++) {
if (strcmp(res[i].a,tmp) == 0) {
flag = false;
}
}
if (flag) {
copy_s(tmp, res[idx++].a, e-s+2);
//printf("%s\n",tmp);
}
}
}
void clear_buf(){
for(int i = 0; i < 26; i++) {
l[i] = 0;
}
}
void print_lucky_string_of_c(char * buf, int n, char c, struct data res[]) {
int st = find_next_c(buf, c, 0, n);
while (st != -1) {
//printf("new circle!\n");
int count = 1;
print_buf(buf,st,st, res);
l[c-'a'] += 1;
int i = st + 1;
while (i < n) {
if (l[buf[i]-'a'] == 0) {
count++;
}
l[buf[i]-'a']++;
if (find_lucky(count) != -1) {
print_buf(buf,st,i,res);
//printf("%d-%d-%d\n",count,st,i);
}
i++;
}
st = find_next_c(buf, c, st+1, n);
clear_buf();
}
}
int main()
{
char s[10000];
scanf("%s", s);
int n = strlen(s);
/*
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 < 26; i++) {
idx = 0;
struct data res[10000];
print_lucky_string_of_c(s, n , 'a' + i, res);
//printf("n=%d",idx);
//printf("%s\n",res[9]);
qsort(res, idx, sizeof(struct data), cmp);
//printf("idx=%d",idx);
//printf("%s\n",res[9]);
for(int i = 0; i < idx; i++) {
printf("%s\n",res[i]); //printf("--%s\n",res[i]); error
}
}
/*
//列出所有子序列
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]);
}
*/
}
Rust 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-05-12
use std::io;
use std::collections::{HashSet, BTreeSet};
fn main() {
let fibonacci = [1, 2, 3, 5, 8, 13, 21].iter().map(|num| *num).collect::<HashSet<i32>>();
let mut s = String::new();
io::stdin().read_line(&mut s);
let s = s.trim().chars().collect::<Vec<char>>();
let n = s.len();
let mut res = BTreeSet::new();
for i in 0..n {
let mut chrs = HashSet::new();
for j in i..n {
chrs.insert(s[j]);
if fibonacci.contains(&(chrs.len() as i32)) {
res.insert(s[i..=j].iter().collect::<String>());
}
}
}
print!("{}", res.into_iter().collect::<Vec<String>>().join("\n"));
}
C 解法, 执行用时: 2ms, 内存消耗: 492KB, 提交时间: 2020-03-28
#include<stdio.h>
#include<string.h>
int fi[27]={0};
int m=0,n,num[26];
char e[10001][100];
int Comp(const void*x,const void*y)
{ return strcmp(e[*(int*)x],e[*(int*)y]);
}
int main()
{
int i,j,k,a[10001];
char c[101];
fi[1]=fi[2]=fi[3]=fi[5]=fi[8]=fi[13]=fi[21]=1;
gets(c);
for(i=0;c[i];i++){
n=0;
memset(num,0,26*sizeof(int));
for(j=i;c[j];j++){
if(!num[c[j]-'a']++)n++;
if(fi[n]){
for(k=0;k<=j-i;k++)e[m][k]=c[i+k];
e[m++][k]=0;
}
}
}
for(i=0;i<m;i++)a[i]=i;
qsort(a,m,sizeof(int),Comp);
puts(e[a[0]]);
for(i=1;i<m;i++)if(strcmp(e[a[i]],e[a[i-1]]))puts(e[a[i]]);
}
C++ 解法, 执行用时: 2ms, 内存消耗: 512KB, 提交时间: 2021-05-22
//1 1 2 3 5 8 13 21
#include<bits/stdc++.h>
using namespace std;
string s;
vector<string> res;
bool vis[27];
int main() {
cin >> s;
vis[1] = true; vis[2] = true; vis[3] = true; vis[5] = true; vis[8] = true;
vis[13] =true; vis[21] = true;
for (int i = 0; i < s.size(); ++i) {
int st = 0;
string t = "";
for (int j = i; j < s.size(); ++j) {
st|= 1<<s[j]-'a';
t += s[j];
if(vis[__builtin_popcount(st)])res.emplace_back(t);
}
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
for (int i = 0; i < res.size(); ++i) cout << res[i] << "\n";
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 364KB, 提交时间: 2019-11-29
#include<stdio.h>
#include<string.h>
int fi[27]={0};
int m=0,n,num[26];
char e[10001][100];
int Comp(const void*x,const void*y)
{ return strcmp(e[*(int*)x],e[*(int*)y]);
}
int main()
{
int i,j,k,a[10001];
char c[101];
fi[1]=fi[2]=fi[3]=fi[5]=fi[8]=fi[13]=fi[21]=1;
gets(c);
for(i=0;c[i];i++){
n=0;
memset(num,0,26*sizeof(int));
for(j=i;c[j];j++){
if(!num[c[j]-'a']++)n++;
if(fi[n]){
for(k=0;k<=j-i;k++)e[m][k]=c[i+k];
e[m++][k]=0;
}
}
}
for(i=0;i<m;i++)a[i]=i;
qsort(a,m,sizeof(int),Comp);
puts(e[a[0]]);
for(i=1;i<m;i++)if(strcmp(e[a[i]],e[a[i-1]]))puts(e[a[i]]);
}