hihocoder 1152 Lucky Substrings

#1152 : Lucky Substrings

时间限制: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.

样例输入

aabcd

样例输出

a
aa
aab
aabc
ab
abc
b
bc
bcd
c
cd
d

题目大意：给定一个只包含小写字母的字符串S。对于S的任意一个非空子串，若其包含的不同字母个数为fibonacci数列中的数，
则我们认为这个子串为幸运的。请找出S的所有幸运的子串。不要重复输出。

解题思路

一个简单的解题思路是直接枚举S的所有子串，并对其不同字母个数进行统计。

S均由小写字母组成，因此其包含的不同字母个数最多为26个。而在26以内且属于fibonacci数列的数为1,2,3,5,8,13,21。因此只有当子串中不同字母的个数为1,2,3,5,8,13,21时，该子串才是幸运的。

接下来即是如何统计一个子串的不同字母个数，下面给出一种比较朴素的方法：

isLucky(subString):
    alphabet[] = false
    count = 0
    For c in subString
        If not alphabet[c] Then
            alphabet[c] = true
            count = count + 1
        End If
    End For
    Return (count is Fibonaccid number)

S的最大长度为 N = 100，该朴素算法的时间复杂度为O(N^3)，是可以通过所有数据的。

同时，我们可以通过一个小的优化，将算法的时间复杂度减少的O(N^2)。

在已经知道S[i..j]字母个数的情况下，我们可以直接推导出S[i..j+1]的不同字母个数。

首先我们需要改进isLucky函数：

alphabet[] = false
count = 0
isLucky(c):
    If not alphabet[c] Then
        alphabet[c] = true
        count = count + 1
    End If
    Return (count is Fibonaccid number)

这里我们把alphabet和count从函数中抽取出来，作为了全局变量。同时，isLucky的参数变为单个字符，每次将新增的S[j+1]加入统计中。

下面是函数的主体部分：

For i = 0 .. len - 1
    alphabet[] = false
    count = 0
    For j = i .. len - 1
        // 此时isLucky返回的是S[i..j]的不同字母数量是否满足条件
        If isLucky(S[j]) Then
            ansList.push(S[i..j])
        End If
    End For
End For

最后只需要将ansList所保存的子串进行排序去重后输出，即可顺利通过该题目。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <set>
using namespace std;
string s;

bool IsFibonaccidNum(int n){
    return (n == 1 || n == 2 || n == 3 || n == 5 || n == 8 || n == 13 || n == 21);
}

bool isLucky(int i, int j){
    int alphabet[26] = {0};
    //memset(alphabet, 0, sizeof(alphabet));
    int count = 0;
    for(int k = i; k <= j; k++){
        if(alphabet[s[k] - 'a'] == 0){
            alphabet[s[k] - 'a'] = 1;
            count++;
        }
    }
    return (IsFibonaccidNum(count));
}

int main(){
    set<string> set1;
    cin >> s;
    int len = s.length();
    for(int i = 0; i < len; i++){
        for(int j = i; j < len; j++){
            if(isLucky(i, j)){
                string str = s.substr(i, j - i + 1);
                set1.insert(str);
            }
        }
    }
    
    for(set<string>::iterator it = set1.begin(); it != set1.end(); it++){
        cout << *it << endl;
    }
    //system("pause");
    return 0;
}

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <set>
using namespace std;
int alphabet[26] = {0}, cnt;

bool IsFibonaccidNum(int n){
    return (n == 1 || n == 2 || n == 3 || n == 5 || n == 8 || n == 13 || n == 21);
}

bool isLucky(char c){
        if(alphabet[c - 'a'] == 0){
            alphabet[c - 'a'] = 1;
            cnt++;
        }
    return (IsFibonaccidNum(cnt));
}

int main(){
    set<string> set1;
    string s;
    cin >> s;
    int len = s.length();
    for(int i = 0; i < len; i++){
        memset(alphabet, 0, sizeof(alphabet));
        cnt = 0;
        for(int j = i; j < len; j++){
            if(isLucky(s[j])){
                string str = s.substr(i, j - i + 1);
                set1.insert(str);
            }
        }
    }
    
    for(set<string>::iterator it = set1.begin(); it != set1.end(); it++){
        cout << *it << endl;
    }
    //system("pause");
    return 0;
}