题目描述
FST是一名可怜的 OIer,他很强,但是经常 fst,所以 rating 一直低迷。
但是重点在于,他真的很强!他发明了一种奇特的加密方式,这种加密方式只有OIer
才能破解。
这种加密方式是这样的:对于一个 01 串,他会构造另一个 01 串,使得原串是在新串中没有出现过的最短的串。
现在 FST 已经加密好了一个串,但是他的加密方式有些 BUG ,导致没出现过的最短的串不止一个,他感觉非常懊恼,所以他希望计算出没出现过的最短的串的长度。
输入格式
一行,一个 01 串。
输出格式
一行,一个正整数,表示没有出现过的最短串的长度。
样例数据 1
输入
输出
备注
【数据范围】
测试点 1、2、3 的串长度≤10;
测试点 3、4、5 的串长度≤100;
测试点 6、7、8、9、10 的串长度≤10^5;
题目分析
注意到$2^{20}$左右已经超过maxn了,所以肯定不会枚举完所有情况。
先将每个点放入队列,然后每次都往后加一个字符,这样之前必定要删除最后一个点(末尾没有可加入的字符),然后将队列中的每个字符串算出hash,去重计数,如果cnt < $2^{len}$,那么就输出len即为答案。
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<vector>
#include<set>
using namespace std; const int N = 1e5 + ;
string s;
string t[N];
int pos[N];
int cnt;
int hashVal[N];
bool hash[N];
typedef long long ll;
ll pow2[]; inline int read(){
int i = , f = ; char ch = getchar();
for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());
if(ch == '-') f = -, ch = getchar();
for(; ch >= '' && ch <= ''; ch = getchar())
i = (i << ) + (i << ) + (ch - '');
return i * f;
} inline void wr(int x){
if(x < ) putchar('-'), x = -x;
if(x > ) wr(x / );
putchar(x % + '');
} inline void initPow2(){
pow2[] = ;
for(int i = ; i <= ; i++)
pow2[i] = pow2[i - ] * ;
} int main(){
initPow2();
cin >> s;
int len = s.length();
string tmp = "";
for(int i = ; i < len; i++)
t[i] = "", pos[i] = i - , hashVal[i] = ;
cnt = len;
int leng = ;
while(cnt){
memset(hash, , sizeof hash);
leng++; int ans = ;
for(int i = ; i < cnt; i++){
t[i] += s[++pos[i]];
hashVal[i] *= ;
if(s[pos[i]] == '')
hashVal[i]++;
int h = hashVal[i];
if(!hash[h]) ans++, hash[h] = true;
}
if(ans < pow2[leng]){
wr(leng);
return ;
}
cnt--;
}
wr();
return ;
}