Problem A. Lucky Substrings

Source

Problem

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

样例输出

  1. a
  2. aa
  3. aab
  4. aabc
  5. ab
  6. abc
  7. b
  8. bc
  9. bcd
  10. c
  11. cd
  12. d

题解

简单实现题，即判断 substring 中不同字符串的个数是否为 fibonacci 数，最后以字典序方式输出，且输出的字符串中相同的只输出一次。分析下来需要做如下几件事：

  1. 两重 for 循环取输入字符串的所有可能子串。
  2. 判断子串中不同字符的数目，这里使用可以去重的数据结构Set比较合适，最后输出Set的大小即为不同字符的数目。
  3. 判断不同字符数是否为 fibonacci 数，由于子串数目较多，故 fibonacci 应该首先生成，由于字符串输入最大长度为100，故使用哈希表这种查询时间复杂度为 $$O(1)$$ 的数据结构。
  4. 将符合条件的子串加入到最终结果，由于结果需要去重，故选用Set数据结构。

Java

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner in = new Scanner(System.in);
  6.         String input = in.nextLine();
  7.         Set<String> result = solve(input);
  8.         for (String s : result) {
  9.             System.out.println(s);
  10.         }
  11.     }
  13.     public static Set<String> solve(String input) {
  14.         Set<Long> fibonacci = fibonacci_number(input.length());
  15.         Set<String> res = new TreeSet<String>();
  16.         for (int i = 0; i < input.length(); i++) {
  17.             for (int j = i + 1; j <= input.length(); j++) {
  18.                 String substr = input.substring(i, j);
  19.                 if (isFibonacci(substr, fibonacci)) {
  20.                     res.add(substr);
  21.                 }
  22.             }
  23.         }
  25.         return res;
  26.     }
  28.     public static boolean isFibonacci(String s, Set<Long> fibo) {
  29.         Set<Character> charSet = new HashSet<Character>();
  30.         for (Character c : s.toCharArray()) {
  31.             charSet.add(c);
  32.         }
  33.         // convert charSet.size() to long
  34.         if (fibo.contains((long)charSet.size())) {
  35.             return true;
  36.         } else {
  37.             return false;
  38.         }
  39.     }
  41.     public static Set<Long> fibonacci_number(int n) {
  42.         // generate fibonacci number till n
  43.         Set<Long> fibonacci = new HashSet<Long>();
  44.         long fn2 = 1, fn1 = 1, fn = 1;
  45.         fibonacci.add(fn);
  46.         for (int i = 3; i <= n; i++) {
  47.             fn = fn1 + fn2;
  48.             fibonacci.add(fn);
  49.             fn2 = fn1;
  50.             fn1 = fn;
  51.         }
  52.         return fibonacci;
  53.     }
  54. }

源码分析

fibonacci 数组的生成使用迭代的方式，由于保存的是Long类型，故在判断子串 size 时需要将 size 转换为long. Java 中常用的 Set 有两种，无序的HashSet和有序的TreeSet.

复杂度分析

遍历所有可能子串，时间复杂度 O(n^2), fibonacci 数组和临时子串，空间复杂度 O(n).