HDU4886 TIANKENG’s restaurant(Ⅱ)(哈希)

题意：

一个字符串有许多子串  现要找出最短的字典序最小的不是它的子串的串  这个长串只有A~H字母

分析：

首先估计下答案的最长长度，如果答案的长度为7，那么字符串种类就有8^7种，已经超过了所给字符串的最大长度1000000。那么只需要枚举长度  利用哈希判定字符串出现的问题。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
char str[maxn];
int Hash[maxn], vis[maxn];
int main()
{
    int T, i, j, len;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str+1);
        len = strlen(str+1);
        memset(Hash, 0, sizeof(Hash));
        memset(vis, 0, sizeof(vis));
        int lim = 8, ans;
        for(i = 1; i <= 7; i++)
        {
            for(j = len; j >= i; j--)
            {
                Hash[j] = Hash[j-1]*8 + str[j] - 'A';
                vis[Hash[j]]++;
            }
            for(j = 0; j < lim; j++)
            {
                if(!vis[j])
                {
                    ans = j;
                    goto gt;
                }
                vis[j] = 0;
            }
            lim *= 8;
        }
    gt:
        j = 0;
        while(i--)
        {
            str[j++] = ans % 8 + 'A';
            ans /= 8;
        }
        for(i = j - 1; i >= 0; i--)
            printf("%c", str[i]);
        puts("");
    }
    return 0;
}