首页 > 代码库 > HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )

HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )

2024-08-06 23:26:35   234人阅读

TIANKENG’s restaurant(Ⅱ)

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 130107/65536 K (Java/Others)
Total Submission(s): 466    Accepted Submission(s): 153


Problem Description
After improving the marketing strategy, TIANKENG has made a fortune and he is going to step into the status of TuHao. Nevertheless, TIANKENG wants his restaurant to go international, so he decides to name his restaurant in English. For the lack of English skills, TIANKENG turns to CC, an English expert, to help him think of a property name. CC is a algorithm lover other than English, so he gives a long string S to TIANKENG. The string S only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’. TIANKENG wants his restaurant’s name to be out of ordinary, so the restaurant’s name is a string T which should satisfy the following conditions: The string T should be as short as possible, if there are more than one strings which have the same shortest length, you should choose the string which has the minimum lexicographic order. Could you help TIANKENG get the name as soon as possible?

Meanwhile, T is different from all the substrings of S. Could you help TIANKENG get the name as soon as possible?
 

 

Input
The first line input file contains an integer T(T<=50) indicating the number of case.
In each test case:
Input a string S. the length of S is not large than 1000000.
 

 

Output
For each test case:
Output the string t satisfying the condition.(T also only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’.)
 

 

Sample Input
3
ABCDEFGH
AAABAACADAEAFAGAH
ACAC
 

 

Sample Output
AA
BB
B
 

 

因为只有8个字母 。

那么先枚举长度 （ i = 1 ~ 8 ）。

O(n)处理出该长度下主串存在的子串。

再枚举排列 （ j = 0 ~ i ! ）判存。

 

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <map>#include <set>#include <stack>#include <algorithm>using namespace std;typedef long long LL;typedef pair<int,int> pii;const int N = 1000010;const int M = 43046721;const int inf = 1e9+7;const double eps = 1e-8;bool vis[M];char str[N];int a[N],f[N],len;void get_s( int n , int cnt ,char *s) {    for( int i = cnt-1 ; i >= 0 ; --i ){        s[i] = (n%8)+‘A‘;        n/=8;    }    s[cnt] = 0 ;}int check( int n ) {    int tmp = 0 ;    if( len < n ) return -1;    for( int i = 0 ; i < f[n] ; ++i ) vis[i] = false ;    for( int i = 0 ; i < n ; ++i )        tmp = tmp * 8 + a[i] ;    vis[tmp] = true ;    for( int i = n ; i < len ; ++i ){        tmp = ( tmp % f[n-1] ) * 8 + a[i] ;        vis[tmp] = true ;    }    for( int i = 0 ; i < f[n] ; ++i )if(!vis[i]){        return i ;    }    return -1 ;}void Run(){    scanf("%s",str); len = strlen(str);    for( int i = 0 ; i < len ; ++i ) a[i] = str[i]-‘A‘;    for( int i = 1 ; i <= 8 ; ++i ){        int res = check(i) ;        if( res == -1 ) continue ;        get_s(res,i,str) ;        puts(str);        return ;    }}int main(){    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif // LOCAL    int tot = 1 , m = 1 ; f[0] = 1 ;    for( int i = 0 ; i < 8 ; ++i ) m *=8 ,f[tot++] = m ;    int _ ; scanf("%d",&_);    while( _-- ) Run();}
View Code

 

HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )


联系
我们