首页 > 代码库 > HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )
HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )
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?
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.
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’.)
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();}
HDU 4886 TIANKENG’s restaurant(Ⅱ) ( 暴力+hash )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。