# 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<String> result = solve(input); for (String s : result) { System.out.println(s); } } public static Set<String> solve(String input) { Set<Long> fibonacci = fibonacci_number(input.length()); Set<String> res = new TreeSet<String>(); 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<Long> fibo) { Set<Character> charSet = new HashSet<Character>(); 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<Long> fibonacci_number(int n) { // generate fibonacci number till n Set<Long> fibonacci = new HashSet<Long>(); 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).