CSU2188: Substring

Description

FST 是一名可怜的 ACMer，他很强，但是经常 fst，所以 rating 一直低迷。但是重点在于，他真的很强!他发明了一种奇特的加密方式，这种加密方式只有 ACMer 才能破解。这种加密方式是这样的:对于一个 01 串，他会构造另一个 01 串，使得原串是在新串中没有出现过的最短的串。现在 FST 已经加密好了一个串，但是他的加密方式有些 BUG，导致没出现过的最短的串不止一个，他感觉非常懊恼，所以他希望计算出没出现过的最短的串的长度。

Input

单组数据一行，一个 01 串，字符串串长小于等于10^ 5

Output

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

Sample Input

100010110011101

Sample Output

4

题意：在一个很长的串内找到一个没有出现过最短的子串，由于串比较长，所以我们不能直接对于字符串进行处理。我们可以换一个思想，从答案的长度入手，每次枚举答案的长度，然后把这个很长的子串拆分很多这个长度的子串，
放到set当中存储，利用set的去重，如果最后的set的size()<2^（ans）也就是小于我们枚举长度能产生所有的可能的串的数量，那么就说明当中肯定有一个串没有出现过。
就可以得到答案。

这题也可以用字符串hash去做，时间复杂度会比set+string的要小些。但是思想是一样的。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

using namespace std;

string s;

set<string>ss;

int main()

{

    cin>>s;

    int len=s.length();

    string temp="";

    int ans=1;

    while(1)

    {

        ss.clear();

        for(int i=0;i<=len-ans;i++)

        {

//            cout<<i<<endl;

            for(int j=i;j<i+ans;j++)

            {

                temp+=s[j];

            }

//            cout<<temp<<endl;

            ss.insert(temp);

            temp="";

        }

//        cout<<ss.size()<<endl;

        if(ss.size()<pow(2,ans))

            break;

        else

            ans++;

    }

    printf("%d\n",ans);

    return 0;

}

/**********************************************************************

	Problem: 2188

	User: therang

	Language: C++

	Result: AC

	Time:540 ms

	Memory:3580 kb

**********************************************************************/

巴特西