【题解】子串最小数

题意

给你一个由组成的长度为的字符串。问该串中没出现过的子串中所代表的整数最小值是多少。例如，，其中没有出现过的最小整数为。

题解

如果要保证每一个数都在串中出现，那么该串最长会长这样，由于题目给的串长度只有，所以，所以没出现的过的数其长度最多为。我们可以把所有长度为的子串存起来，然后看那个数字没出现过，这个时候就可以用整数哈希了，由于数字里面没有出，我们可以用进制来哈希，进制下表示串中的。我们直接去暴力去找那个数字没出现过即可。
##复杂度
时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char str[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        int n=strlen(str);
        int maxn=1;
        int flag=0;
        for(int i=1;i<=6;i++)
        {
            maxn*=9;
            map<int,int>vis;
            for(int j=0;j<n;j++)
            {
                int sum=0;
                for(int k=j;k<j+i&&k<n;k++)
                    sum=sum*9+str[k]-'1';
                vis[sum]++;
            }
            for(int j=0;j<maxn;j++)
            {
                if(!vis[j])
                {
                    int tmp=j;
                    string ans="";
                    for(int k=0;k<i;k++)
                    {
                        ans+='1'+tmp%9;
                        tmp/=9;
                    }
                    reverse(ans.begin(),ans.end());
                    cout<<ans<<endl;
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
        }
    }
    return 0;
}