【noip模拟】Fancy Signal Translate (暴力 + 哈希)

题目描述

FST是一名可怜的 OIer，他很强，但是经常 fst，所以 rating 一直低迷。

但是重点在于，他真的很强！他发明了一种奇特的加密方式，这种加密方式只有OIer
才能破解。

这种加密方式是这样的：对于一个 01 串，他会构造另一个 01 串，使得原串是在新串中没有出现过的最短的串。

现在 FST 已经加密好了一个串，但是他的加密方式有些 BUG ，导致没出现过的最短的串不止一个，他感觉非常懊恼，所以他希望计算出没出现过的最短的串的长度。

输入格式

一行，一个 01 串。

输出格式

一行，一个正整数，表示没有出现过的最短串的长度。

样例数据 1

输入

100010110011101

输出

4

备注

【数据范围】
测试点 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 + 5;
string s;
string t[N];
int pos[N];
int cnt;
int hashVal[N];
bool hash[N];
typedef long long ll;
ll pow2[50];

inline int read(){
    int i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(int x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
} 

inline void initPow2(){
    pow2[0] = 1;
    for(int i = 1; i <= 30; i++)
        pow2[i] = pow2[i - 1] * 2;
}

int main(){
    initPow2();
    cin >> s;
    int len = s.length();
    string tmp = "";
    for(int i = 0; i < len; i++)
        t[i] = "", pos[i] = i - 1, hashVal[i] = 0;
    cnt = len;
    int leng = 0;
    while(cnt){
        memset(hash, 0, sizeof hash);
        leng++; int ans = 0;
        for(int i = 0; i < cnt; i++){
            t[i] += s[++pos[i]];
            hashVal[i] *= 2;
            if(s[pos[i]] == '1')
                hashVal[i]++;
            int h = hashVal[i];
            if(!hash[h]) ans++, hash[h] = true;
        }
        if(ans < pow2[leng]){
            wr(leng);
            return 0;
        }
        cnt--;
    }
    wr(0);
    return 0;
}