Problem A. Lucky Substrings
最后更新于：2022-04-02 01:15:06
# Problem A. Lucky Substrings
### Source
- [hihoCoder](http://hihocoder.com/problemset/problem/1152)
### Problem
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
### 描述
A string s is **LUCKY** if and only if the number of different characters in sis a [fibonacci number](http://en.wikipedia.org/wiki/Fibonacci_number). Givena string consisting of only lower case letters, output all its lucky non-emptysubstrings 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. Samesubstrings should be printed once.
样例输入
~~~
aabcd
~~~
样例输出
~~~
a
aa
aab
aabc
ab
abc
b
bc
bcd
c
cd
d
~~~
### 题解
简单实现题，即判断 substring 中不同字符串的个数是否为 fibonacci 数，最后以字典序方式输出，且输出的字符串中相同的只输出一次。分析下来需要做如下几件事：
1. 两重 for 循环取输入字符串的所有可能子串。
1. 判断子串中不同字符的数目，这里使用可以去重的数据结构`Set`比较合适，最后输出`Set`的大小即为不同字符的数目。
1. 判断不同字符数是否为 fibonacci 数，由于子串数目较多，故 fibonacci 应该首先生成，由于字符串输入最大长度为100，故使用哈希表这种查询时间复杂度为 O(1)O(1)O(1) 的数据结构。
1. 将符合条件的子串加入到最终结果，由于结果需要去重，故选用`Set`数据结构。
### Java
~~~
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String input = in.nextLine();
Set result = solve(input);
for (String s : result) {
System.out.println(s);
}
}
public static Set solve(String input) {
Set fibonacci = fibonacci_number(input.length());
Set res = new TreeSet();
for (int i = 0; i < input.length(); i++) {
for (int j = i + 1; j <= input.length(); j++) {
String substr = input.substring(i, j);
if (isFibonacci(substr, fibonacci)) {
res.add(substr);
}
}
}
return res;
}
public static boolean isFibonacci(String s, Set fibo) {
Set charSet = new HashSet();
for (Character c : s.toCharArray()) {
charSet.add(c);
}
// convert charSet.size() to long
if (fibo.contains((long)charSet.size())) {
return true;
} else {
return false;
}
}
public static Set fibonacci_number(int n) {
// generate fibonacci number till n
Set fibonacci = new HashSet();
long fn2 = 1, fn1 = 1, fn = 1;
fibonacci.add(fn);
for (int i = 3; i <= n; i++) {
fn = fn1 + fn2;
fibonacci.add(fn);
fn2 = fn1;
fn1 = fn;
}
return fibonacci;
}
}
~~~
### 源码分析
fibonacci 数组的生成使用迭代的方式，由于保存的是`Long`类型，故在判断子串 size 时需要将 size 转换为`long`. Java 中常用的 Set 有两种，无序的`HashSet`和有序的`TreeSet`.
### 复杂度分析
遍历所有可能子串，时间复杂度 O(n2)O(n^2)O(n2), fibonacci 数组和临时子串，空间复杂度 O(n)O(n)O(n).
';