Monthly Archives: February 2016

hihoCoder week 84-1-Lucky Substrings

hihoCoder week 84-1-Lucky Substrings
题目1 : 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


如果一个字符串中不同字母的个数是斐波那契数,则称这个字符串是Lucky的,问字符串S中哪些子串是Lucky子串。
要正确理解Lucky的定义,是不同字母的个数,而不是不同字母的个数序列。比如aabc是Lucky的,因为其有a,b,c共3种字母,而3在斐波那契数列中,所以aabc是Lucky的。不能理解为aabc中a出现2次,b,c分别出现1次,构成1,1,3是斐波那契数列,所以aabc是Lucky的。
所以只能枚举所有子串,判断每个子串是否为Lucky的。如果知道了S[i,...,j]中不同字母的个数,判断S[i,...,j+1]时,只要判断S[j+1]这个字母是否在之前出现过。所以通过保存之前不同字母的个数,可以快速判断S[i,...,j+1]的情况。
完整代码如下:

#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
set<int> FIB_NUM = { 1,2,3,5,8,13,21 };
int main() {
	string s;
	cin >> s;
	set<string> ans;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		vector<bool> alphabet(26, false);
		int cnt = 0;
		for (int j = i; j < n; j++) {
			if (!alphabet[s[j] - 'a']) {
				alphabet[s[j] - 'a'] = true;
				cnt++;
			}
			if (FIB_NUM.find(cnt) != FIB_NUM.end()) {
				ans.insert(s.substr(i, j - i + 1));
			}
		}
	}
	set<string>::iterator it = ans.begin();
	while (it != ans.end()) {
		cout << *it << endl;
		it++;
	}
	return 0;
}

本代码提交AC,用时17MS,内存0MB。